states: remove unused check_stack_free() function
[smatch.git] / smatch_comparison.c
blobc15be3eae1ade6a3714ddfaceefa730254467ecc
1 /*
2 * Copyright (C) 2012 Oracle.
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.
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.
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
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 ">=".
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.
31 #include "smatch.h"
32 #include "smatch_extra.h"
33 #include "smatch_slist.h"
35 static int compare_id;
36 static int link_id;
38 struct compare_data {
39 const char *var1;
40 struct var_sym_list *vsl1;
41 int comparison;
42 const char *var2;
43 struct var_sym_list *vsl2;
45 ALLOCATOR(compare_data, "compare data");
47 int chunk_vsl_eq(const char *a, struct var_sym_list *a_vsl, const char *b, struct var_sym_list *b_vsl)
49 if (strcmp(a, b) == 0)
50 return 1;
51 return 0;
54 static struct symbol *vsl_to_sym(struct var_sym_list *vsl)
56 struct var_sym *vs;
58 if (!vsl)
59 return NULL;
60 if (ptr_list_size((struct ptr_list *)vsl) != 1)
61 return NULL;
62 vs = first_ptr_list((struct ptr_list *)vsl);
63 return vs->sym;
66 static struct smatch_state *alloc_compare_state(
67 const char *var1, struct var_sym_list *vsl1,
68 int comparison,
69 const char *var2, struct var_sym_list *vsl2)
71 struct smatch_state *state;
72 struct compare_data *data;
74 state = __alloc_smatch_state(0);
75 state->name = alloc_sname(show_special(comparison));
76 data = __alloc_compare_data(0);
77 data->var1 = alloc_sname(var1);
78 data->vsl1 = clone_var_sym_list(vsl1);
79 data->comparison = comparison;
80 data->var2 = alloc_sname(var2);
81 data->vsl2 = clone_var_sym_list(vsl2);
82 state->data = data;
83 return state;
86 static int state_to_comparison(struct smatch_state *state)
88 if (!state || !state->data)
89 return 0;
90 return ((struct compare_data *)state->data)->comparison;
94 * flip_op() reverses the op left and right. So "x >= y" becomes "y <= x".
96 static int flip_op(int op)
98 switch (op) {
99 case 0:
100 return 0;
101 case '<':
102 return '>';
103 case SPECIAL_UNSIGNED_LT:
104 return SPECIAL_UNSIGNED_GT;
105 case SPECIAL_LTE:
106 return SPECIAL_GTE;
107 case SPECIAL_UNSIGNED_LTE:
108 return SPECIAL_UNSIGNED_GTE;
109 case SPECIAL_EQUAL:
110 return SPECIAL_EQUAL;
111 case SPECIAL_NOTEQUAL:
112 return SPECIAL_NOTEQUAL;
113 case SPECIAL_GTE:
114 return SPECIAL_LTE;
115 case SPECIAL_UNSIGNED_GTE:
116 return SPECIAL_UNSIGNED_LTE;
117 case '>':
118 return '<';
119 case SPECIAL_UNSIGNED_GT:
120 return SPECIAL_UNSIGNED_LT;
121 default:
122 sm_msg("internal smatch bug. unhandled comparison %d", op);
123 return op;
127 static int falsify_op(int op)
129 switch (op) {
130 case 0:
131 return 0;
132 case '<':
133 return SPECIAL_GTE;
134 case SPECIAL_UNSIGNED_LT:
135 return SPECIAL_UNSIGNED_GTE;
136 case SPECIAL_LTE:
137 return '>';
138 case SPECIAL_UNSIGNED_LTE:
139 return SPECIAL_UNSIGNED_GT;
140 case SPECIAL_EQUAL:
141 return SPECIAL_NOTEQUAL;
142 case SPECIAL_NOTEQUAL:
143 return SPECIAL_EQUAL;
144 case SPECIAL_GTE:
145 return '<';
146 case SPECIAL_UNSIGNED_GTE:
147 return SPECIAL_UNSIGNED_LT;
148 case '>':
149 return SPECIAL_LTE;
150 case SPECIAL_UNSIGNED_GT:
151 return SPECIAL_UNSIGNED_LTE;
152 default:
153 sm_msg("internal smatch bug. unhandled comparison %d", op);
154 return op;
158 static int rl_comparison(struct range_list *left_rl, struct range_list *right_rl)
160 sval_t left_min, left_max, right_min, right_max;
162 if (!left_rl || !right_rl)
163 return 0;
165 left_min = rl_min(left_rl);
166 left_max = rl_max(left_rl);
167 right_min = rl_min(right_rl);
168 right_max = rl_max(right_rl);
170 if (left_min.value == left_max.value &&
171 right_min.value == right_max.value &&
172 left_min.value == right_min.value)
173 return SPECIAL_EQUAL;
175 if (sval_cmp(left_max, right_min) < 0)
176 return '<';
177 if (sval_cmp(left_max, right_min) == 0)
178 return SPECIAL_LTE;
179 if (sval_cmp(left_min, right_max) > 0)
180 return '>';
181 if (sval_cmp(left_min, right_max) == 0)
182 return SPECIAL_GTE;
184 return 0;
187 static struct range_list *get_orig_rl(struct var_sym_list *vsl)
189 struct symbol *sym;
190 struct smatch_state *state;
192 if (!vsl)
193 return NULL;
194 sym = vsl_to_sym(vsl);
195 if (!sym || !sym->ident)
196 return NULL;
197 state = get_orig_estate(sym->ident->name, sym);
198 return estate_rl(state);
201 static struct smatch_state *unmatched_comparison(struct sm_state *sm)
203 struct compare_data *data = sm->state->data;
204 struct range_list *left_rl, *right_rl;
205 int op;
207 if (!data)
208 return &undefined;
210 if (strstr(data->var1, " orig"))
211 left_rl = get_orig_rl(data->vsl1);
212 else if (!get_implied_rl_var_sym(data->var1, vsl_to_sym(data->vsl1), &left_rl))
213 return &undefined;
214 if (strstr(data->var2, " orig"))
215 right_rl = get_orig_rl(data->vsl2);
216 else if (!get_implied_rl_var_sym(data->var2, vsl_to_sym(data->vsl2), &right_rl))
217 return &undefined;
220 op = rl_comparison(left_rl, right_rl);
221 if (op)
222 return alloc_compare_state(data->var1, data->vsl1, op, data->var2, data->vsl2);
224 return &undefined;
227 /* remove_unsigned_from_comparison() is obviously a hack. */
228 static int remove_unsigned_from_comparison(int op)
230 switch (op) {
231 case SPECIAL_UNSIGNED_LT:
232 return '<';
233 case SPECIAL_UNSIGNED_LTE:
234 return SPECIAL_LTE;
235 case SPECIAL_UNSIGNED_GTE:
236 return SPECIAL_GTE;
237 case SPECIAL_UNSIGNED_GT:
238 return '>';
239 default:
240 return op;
245 * This is for when you merge states "a < b" and "a == b", the result is that
246 * we can say for sure, "a <= b" after the merge.
248 static int merge_comparisons(int one, int two)
250 int LT, EQ, GT;
252 one = remove_unsigned_from_comparison(one);
253 two = remove_unsigned_from_comparison(two);
255 LT = EQ = GT = 0;
257 switch (one) {
258 case '<':
259 LT = 1;
260 break;
261 case SPECIAL_LTE:
262 LT = 1;
263 EQ = 1;
264 break;
265 case SPECIAL_EQUAL:
266 EQ = 1;
267 break;
268 case SPECIAL_GTE:
269 GT = 1;
270 EQ = 1;
271 break;
272 case '>':
273 GT = 1;
276 switch (two) {
277 case '<':
278 LT = 1;
279 break;
280 case SPECIAL_LTE:
281 LT = 1;
282 EQ = 1;
283 break;
284 case SPECIAL_EQUAL:
285 EQ = 1;
286 break;
287 case SPECIAL_GTE:
288 GT = 1;
289 EQ = 1;
290 break;
291 case '>':
292 GT = 1;
295 if (LT && EQ && GT)
296 return 0;
297 if (LT && EQ)
298 return SPECIAL_LTE;
299 if (LT && GT)
300 return SPECIAL_NOTEQUAL;
301 if (LT)
302 return '<';
303 if (EQ && GT)
304 return SPECIAL_GTE;
305 if (GT)
306 return '>';
307 return 0;
311 * This is for if you have "a < b" and "b <= c". Or in other words,
312 * "a < b <= c". You would call this like get_combined_comparison('<', '<=').
313 * The return comparison would be '<'.
315 * This function is different from merge_comparisons(), for example:
316 * merge_comparison('<', '==') returns '<='
317 * get_combined_comparison('<', '==') returns '<'
319 static int combine_comparisons(int left_compare, int right_compare)
321 int LT, EQ, GT;
323 left_compare = remove_unsigned_from_comparison(left_compare);
324 right_compare = remove_unsigned_from_comparison(right_compare);
326 LT = EQ = GT = 0;
328 switch (left_compare) {
329 case '<':
330 LT++;
331 break;
332 case SPECIAL_LTE:
333 LT++;
334 EQ++;
335 break;
336 case SPECIAL_EQUAL:
337 return right_compare;
338 case SPECIAL_GTE:
339 GT++;
340 EQ++;
341 break;
342 case '>':
343 GT++;
346 switch (right_compare) {
347 case '<':
348 LT++;
349 break;
350 case SPECIAL_LTE:
351 LT++;
352 EQ++;
353 break;
354 case SPECIAL_EQUAL:
355 return left_compare;
356 case SPECIAL_GTE:
357 GT++;
358 EQ++;
359 break;
360 case '>':
361 GT++;
364 if (LT == 2) {
365 if (EQ == 2)
366 return SPECIAL_LTE;
367 return '<';
370 if (GT == 2) {
371 if (EQ == 2)
372 return SPECIAL_GTE;
373 return '>';
375 return 0;
378 static struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
380 struct compare_data *data = s1->data;
381 int op;
383 op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
384 if (op)
385 return alloc_compare_state(data->var1, data->vsl1, op, data->var2, data->vsl2);
386 return &undefined;
389 static struct smatch_state *alloc_link_state(struct string_list *links)
391 struct smatch_state *state;
392 static char buf[256];
393 char *tmp;
394 int i;
396 state = __alloc_smatch_state(0);
398 i = 0;
399 FOR_EACH_PTR(links, tmp) {
400 if (!i++) {
401 snprintf(buf, sizeof(buf), "%s", tmp);
402 } else {
403 append(buf, ", ", sizeof(buf));
404 append(buf, tmp, sizeof(buf));
406 } END_FOR_EACH_PTR(tmp);
408 state->name = alloc_sname(buf);
409 state->data = links;
410 return state;
413 static void save_start_states(struct statement *stmt)
415 struct symbol *param;
416 char orig[64];
417 char state_name[128];
418 struct smatch_state *state;
419 struct string_list *links;
420 char *link;
422 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
423 struct var_sym_list *vsl1 = NULL;
424 struct var_sym_list *vsl2 = NULL;
426 if (!param->ident)
427 continue;
428 snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
429 snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
430 add_var_sym(&vsl1, param->ident->name, param);
431 add_var_sym(&vsl2, orig, param);
432 state = alloc_compare_state(param->ident->name, vsl1, SPECIAL_EQUAL, alloc_sname(orig), vsl2);
433 set_state(compare_id, state_name, NULL, state);
435 link = alloc_sname(state_name);
436 links = NULL;
437 insert_string(&links, link);
438 state = alloc_link_state(links);
439 set_state(link_id, param->ident->name, param, state);
440 } END_FOR_EACH_PTR(param);
443 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
445 struct smatch_state *ret;
446 struct string_list *links;
448 links = combine_string_lists(s1->data, s2->data);
449 ret = alloc_link_state(links);
450 return ret;
453 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
455 struct smatch_state *old_state, *new_state;
456 struct string_list *links;
457 char *new;
459 old_state = get_state(link_id, var, sym);
460 if (old_state)
461 links = clone_str_list(old_state->data);
462 else
463 links = NULL;
465 new = alloc_sname(link);
466 insert_string(&links, new);
468 new_state = alloc_link_state(links);
469 set_state(link_id, var, sym, new_state);
472 static void match_inc(struct sm_state *sm)
474 struct string_list *links;
475 struct smatch_state *state;
476 char *tmp;
478 links = sm->state->data;
480 FOR_EACH_PTR(links, tmp) {
481 state = get_state(compare_id, tmp, NULL);
483 switch (state_to_comparison(state)) {
484 case SPECIAL_EQUAL:
485 case SPECIAL_GTE:
486 case SPECIAL_UNSIGNED_GTE:
487 case '>':
488 case SPECIAL_UNSIGNED_GT: {
489 struct compare_data *data = state->data;
490 struct smatch_state *new;
492 new = alloc_compare_state(data->var1, data->vsl1, '>', data->var2, data->vsl2);
493 set_state(compare_id, tmp, NULL, new);
494 break;
496 default:
497 set_state(compare_id, tmp, NULL, &undefined);
499 } END_FOR_EACH_PTR(tmp);
502 static void match_dec(struct sm_state *sm)
504 struct string_list *links;
505 struct smatch_state *state;
506 char *tmp;
508 links = sm->state->data;
510 FOR_EACH_PTR(links, tmp) {
511 state = get_state(compare_id, tmp, NULL);
513 switch (state_to_comparison(state)) {
514 case SPECIAL_EQUAL:
515 case SPECIAL_LTE:
516 case SPECIAL_UNSIGNED_LTE:
517 case '<':
518 case SPECIAL_UNSIGNED_LT: {
519 struct compare_data *data = state->data;
520 struct smatch_state *new;
522 new = alloc_compare_state(data->var1, data->vsl1, '<', data->var2, data->vsl2);
523 set_state(compare_id, tmp, NULL, new);
524 break;
526 default:
527 set_state(compare_id, tmp, NULL, &undefined);
529 } END_FOR_EACH_PTR(tmp);
532 static int match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
534 if (!mod_expr)
535 return 0;
536 if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
537 return 0;
539 if (mod_expr->op == SPECIAL_INCREMENT) {
540 match_inc(sm);
541 return 1;
543 if (mod_expr->op == SPECIAL_DECREMENT) {
544 match_dec(sm);
545 return 1;
547 return 0;
550 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
552 struct string_list *links;
553 char *tmp;
555 /* Huh??? This needs a comment! */
556 if (match_inc_dec(sm, mod_expr))
557 return;
559 links = sm->state->data;
561 FOR_EACH_PTR(links, tmp) {
562 set_state(compare_id, tmp, NULL, &undefined);
563 } END_FOR_EACH_PTR(tmp);
564 set_state(link_id, sm->name, sm->sym, &undefined);
567 static char *chunk_to_var_sym(struct expression *expr, struct symbol **sym)
569 char *name, *left_name, *right_name;
570 struct symbol *tmp;
571 char buf[128];
573 expr = strip_expr(expr);
574 if (!expr)
575 return NULL;
576 if (sym)
577 *sym = NULL;
579 name = expr_to_var_sym(expr, &tmp);
580 if (name && tmp) {
581 if (sym)
582 *sym = tmp;
583 return name;
585 if (name)
586 free_string(name);
588 if (expr->type != EXPR_BINOP)
589 return NULL;
590 if (expr->op != '-' && expr->op != '+')
591 return NULL;
593 left_name = expr_to_var(expr->left);
594 if (!left_name)
595 return NULL;
596 right_name = expr_to_var(expr->right);
597 if (!right_name) {
598 free_string(left_name);
599 return NULL;
601 snprintf(buf, sizeof(buf), "%s %s %s", left_name, show_special(expr->op), right_name);
602 free_string(left_name);
603 free_string(right_name);
604 return alloc_string(buf);
607 static char *chunk_to_var(struct expression *expr)
609 return chunk_to_var_sym(expr, NULL);
612 static void save_link(struct expression *expr, char *link)
614 char *var;
615 struct symbol *sym;
617 expr = strip_expr(expr);
618 if (expr->type == EXPR_BINOP) {
619 char *chunk;
621 chunk = chunk_to_var(expr);
622 if (!chunk)
623 return;
625 save_link(expr->left, link);
626 save_link(expr->right, link);
627 save_link_var_sym(chunk, NULL, link);
628 return;
631 var = expr_to_var_sym(expr, &sym);
632 if (!var || !sym)
633 goto done;
635 save_link_var_sym(var, sym, link);
636 done:
637 free_string(var);
640 static void update_tf_links(struct state_list *pre_slist,
641 const char *left_var, struct var_sym_list *left_vsl,
642 int left_comparison,
643 const char *mid_var, struct var_sym_list *mid_vsl,
644 struct string_list *links)
646 struct smatch_state *state;
647 struct smatch_state *true_state, *false_state;
648 struct compare_data *data;
649 const char *right_var;
650 struct var_sym_list *right_vsl;
651 int right_comparison;
652 int true_comparison;
653 int false_comparison;
654 char *tmp;
655 char state_name[256];
656 struct var_sym *vs;
658 FOR_EACH_PTR(links, tmp) {
659 state = get_state_slist(pre_slist, compare_id, tmp, NULL);
660 if (!state || !state->data)
661 continue;
662 data = state->data;
663 right_comparison = data->comparison;
664 right_var = data->var2;
665 right_vsl = data->vsl2;
666 if (chunk_vsl_eq(mid_var, mid_vsl, right_var, right_vsl)) {
667 right_var = data->var1;
668 right_vsl = data->vsl1;
669 right_comparison = flip_op(right_comparison);
671 true_comparison = combine_comparisons(left_comparison, right_comparison);
672 false_comparison = combine_comparisons(falsify_op(left_comparison), right_comparison);
674 if (strcmp(left_var, right_var) > 0) {
675 const char *tmp_var = left_var;
676 struct var_sym_list *tmp_vsl = left_vsl;
678 left_var = right_var;
679 left_vsl = right_vsl;
680 right_var = tmp_var;
681 right_vsl = tmp_vsl;
682 true_comparison = flip_op(true_comparison);
683 false_comparison = flip_op(false_comparison);
686 if (!true_comparison && !false_comparison)
687 continue;
689 if (true_comparison)
690 true_state = alloc_compare_state(left_var, left_vsl, true_comparison, right_var, right_vsl);
691 else
692 true_state = NULL;
693 if (false_comparison)
694 false_state = alloc_compare_state(left_var, left_vsl, false_comparison, right_var, right_vsl);
695 else
696 false_state = NULL;
698 snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var);
699 set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
700 FOR_EACH_PTR(left_vsl, vs) {
701 save_link_var_sym(vs->var, vs->sym, state_name);
702 } END_FOR_EACH_PTR(vs);
703 FOR_EACH_PTR(right_vsl, vs) {
704 save_link_var_sym(vs->var, vs->sym, state_name);
705 } END_FOR_EACH_PTR(vs);
706 if (!vsl_to_sym(left_vsl))
707 save_link_var_sym(left_var, NULL, state_name);
708 if (!vsl_to_sym(right_vsl))
709 save_link_var_sym(right_var, NULL, state_name);
710 } END_FOR_EACH_PTR(tmp);
713 static void update_tf_data(struct state_list *pre_slist,
714 const char *left_name, struct symbol *left_sym,
715 const char *right_name, struct symbol *right_sym,
716 struct compare_data *tdata)
718 struct smatch_state *state;
720 state = get_state_slist(pre_slist, link_id, tdata->var2, vsl_to_sym(tdata->vsl2));
721 if (state)
722 update_tf_links(pre_slist, tdata->var1, tdata->vsl1, tdata->comparison, tdata->var2, tdata->vsl2, state->data);
724 state = get_state_slist(pre_slist, link_id, tdata->var1, vsl_to_sym(tdata->vsl1));
725 if (state)
726 update_tf_links(pre_slist, tdata->var2, tdata->vsl2, flip_op(tdata->comparison), tdata->var1, tdata->vsl1, state->data);
729 static void match_compare(struct expression *expr)
731 char *left = NULL;
732 char *right = NULL;
733 struct symbol *left_sym, *right_sym;
734 struct var_sym_list *left_vsl, *right_vsl;
735 int op, false_op;
736 struct smatch_state *true_state, *false_state;
737 char state_name[256];
738 struct state_list *pre_slist;
740 if (expr->type != EXPR_COMPARE)
741 return;
742 left = chunk_to_var_sym(expr->left, &left_sym);
743 if (!left)
744 goto free;
745 left_vsl = expr_to_vsl(expr->left);
746 right = chunk_to_var_sym(expr->right, &right_sym);
747 if (!right)
748 goto free;
749 right_vsl = expr_to_vsl(expr->right);
751 if (strcmp(left, right) > 0) {
752 struct symbol *tmp_sym = left_sym;
753 char *tmp_name = left;
754 struct var_sym_list *tmp_vsl = left_vsl;
756 left = right;
757 left_sym = right_sym;
758 left_vsl = right_vsl;
759 right = tmp_name;
760 right_sym = tmp_sym;
761 right_vsl = tmp_vsl;
762 op = flip_op(expr->op);
763 } else {
764 op = expr->op;
766 false_op = falsify_op(op);
767 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
768 true_state = alloc_compare_state(left, left_vsl, op, right, right_vsl);
769 false_state = alloc_compare_state(left, left_vsl, false_op, right, right_vsl);
771 pre_slist = clone_slist(__get_cur_slist());
772 update_tf_data(pre_slist, left, left_sym, right, right_sym, true_state->data);
773 free_slist(&pre_slist);
775 set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
776 save_link(expr->left, state_name);
777 save_link(expr->right, state_name);
778 free:
779 free_string(left);
780 free_string(right);
783 static void add_comparison_var_sym(const char *left_name,
784 struct var_sym_list *left_vsl,
785 int comparison,
786 const char *right_name, struct var_sym_list *right_vsl)
788 struct smatch_state *state;
789 struct var_sym *vs;
790 char state_name[256];
792 if (strcmp(left_name, right_name) > 0) {
793 const char *tmp_name = left_name;
794 struct var_sym_list *tmp_vsl = left_vsl;
796 left_name = right_name;
797 left_vsl = right_vsl;
798 right_name = tmp_name;
799 right_vsl = tmp_vsl;
800 comparison = flip_op(comparison);
802 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
803 state = alloc_compare_state(left_name, left_vsl, comparison, right_name, right_vsl);
805 set_state(compare_id, state_name, NULL, state);
807 FOR_EACH_PTR(left_vsl, vs) {
808 save_link_var_sym(vs->var, vs->sym, state_name);
809 } END_FOR_EACH_PTR(vs);
810 FOR_EACH_PTR(right_vsl, vs) {
811 save_link_var_sym(vs->var, vs->sym, state_name);
812 } END_FOR_EACH_PTR(vs);
815 static void add_comparison(struct expression *left, int comparison, struct expression *right)
817 char *left_name = NULL;
818 char *right_name = NULL;
819 struct symbol *left_sym, *right_sym;
820 struct var_sym_list *left_vsl, *right_vsl;
821 struct smatch_state *state;
822 char state_name[256];
824 left_name = chunk_to_var_sym(left, &left_sym);
825 if (!left_name)
826 goto free;
827 left_vsl = expr_to_vsl(left);
828 right_name = chunk_to_var_sym(right, &right_sym);
829 if (!right_name)
830 goto free;
831 right_vsl = expr_to_vsl(right);
833 if (strcmp(left_name, right_name) > 0) {
834 struct symbol *tmp_sym = left_sym;
835 char *tmp_name = left_name;
836 struct var_sym_list *tmp_vsl = left_vsl;
838 left_name = right_name;
839 left_sym = right_sym;
840 left_vsl = right_vsl;
841 right_name = tmp_name;
842 right_sym = tmp_sym;
843 right_vsl = tmp_vsl;
844 comparison = flip_op(comparison);
846 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
847 state = alloc_compare_state(left_name, left_vsl, comparison, right_name, right_vsl);
849 set_state(compare_id, state_name, NULL, state);
850 save_link(left, state_name);
851 save_link(right, state_name);
853 free:
854 free_string(left_name);
855 free_string(right_name);
858 static void match_assign_add(struct expression *expr)
860 struct expression *right;
861 struct expression *r_left, *r_right;
862 sval_t left_tmp, right_tmp;
864 right = strip_expr(expr->right);
865 r_left = strip_expr(right->left);
866 r_right = strip_expr(right->right);
868 get_absolute_min(r_left, &left_tmp);
869 get_absolute_min(r_right, &right_tmp);
871 if (left_tmp.value > 0)
872 add_comparison(expr->left, '>', r_right);
873 else if (left_tmp.value == 0)
874 add_comparison(expr->left, SPECIAL_GTE, r_right);
876 if (right_tmp.value > 0)
877 add_comparison(expr->left, '>', r_left);
878 else if (right_tmp.value == 0)
879 add_comparison(expr->left, SPECIAL_GTE, r_left);
882 static void match_assign_sub(struct expression *expr)
884 struct expression *right;
885 struct expression *r_left, *r_right;
886 int comparison;
887 sval_t min;
889 right = strip_expr(expr->right);
890 r_left = strip_expr(right->left);
891 r_right = strip_expr(right->right);
893 if (get_absolute_min(r_right, &min) && sval_is_negative(min))
894 return;
896 comparison = get_comparison(r_left, r_right);
898 switch (comparison) {
899 case '>':
900 case SPECIAL_GTE:
901 if (implied_not_equal(r_right, 0))
902 add_comparison(expr->left, '>', r_left);
903 else
904 add_comparison(expr->left, SPECIAL_GTE, r_left);
905 return;
909 static void match_assign_divide(struct expression *expr)
911 struct expression *right;
912 struct expression *r_left, *r_right;
913 sval_t min;
915 right = strip_expr(expr->right);
916 r_left = strip_expr(right->left);
917 r_right = strip_expr(right->right);
918 if (!get_implied_min(r_right, &min) || min.value <= 1)
919 return;
921 add_comparison(expr->left, '<', r_left);
924 static void match_binop_assign(struct expression *expr)
926 struct expression *right;
928 right = strip_expr(expr->right);
929 if (right->op == '+')
930 match_assign_add(expr);
931 if (right->op == '-')
932 match_assign_sub(expr);
933 if (right->op == '/')
934 match_assign_divide(expr);
937 static void copy_comparisons(struct expression *left, struct expression *right)
939 struct string_list *links;
940 struct smatch_state *state;
941 struct compare_data *data;
942 struct symbol *left_sym, *right_sym;
943 char *left_var = NULL;
944 char *right_var = NULL;
945 struct var_sym_list *left_vsl;
946 const char *var;
947 struct var_sym_list *vsl;
948 int comparison;
949 char *tmp;
951 left_var = chunk_to_var_sym(left, &left_sym);
952 if (!left_var)
953 goto done;
954 left_vsl = expr_to_vsl(left);
955 right_var = chunk_to_var_sym(right, &right_sym);
956 if (!right_var)
957 goto done;
959 state = get_state(link_id, right_var, right_sym);
960 if (!state)
961 return;
962 links = state->data;
964 FOR_EACH_PTR(links, tmp) {
965 state = get_state(compare_id, tmp, NULL);
966 if (!state || !state->data)
967 continue;
968 data = state->data;
969 comparison = data->comparison;
970 var = data->var2;
971 vsl = data->vsl2;
972 if (chunk_vsl_eq(var, vsl, right_var, NULL)) {
973 var = data->var1;
974 vsl = data->vsl1;
975 comparison = flip_op(comparison);
977 add_comparison_var_sym(left_var, left_vsl, comparison, var, vsl);
978 } END_FOR_EACH_PTR(tmp);
980 done:
981 free_string(right_var);
984 static void match_assign(struct expression *expr)
986 struct expression *right;
988 if (expr->op != '=')
989 return;
991 copy_comparisons(expr->left, expr->right);
992 add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
994 right = strip_expr(expr->right);
995 if (right->type == EXPR_BINOP)
996 match_binop_assign(expr);
999 int get_comparison_strings(const char *one, const char *two)
1001 char buf[256];
1002 struct smatch_state *state;
1003 int invert = 0;
1004 int ret = 0;
1006 if (strcmp(one, two) > 0) {
1007 const char *tmp = one;
1009 one = two;
1010 two = tmp;
1011 invert = 1;
1014 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1015 state = get_state(compare_id, buf, NULL);
1016 if (state)
1017 ret = state_to_comparison(state);
1019 if (invert)
1020 ret = flip_op(ret);
1022 return ret;
1025 int get_comparison(struct expression *a, struct expression *b)
1027 char *one = NULL;
1028 char *two = NULL;
1029 int ret = 0;
1031 one = chunk_to_var(a);
1032 if (!one)
1033 goto free;
1034 two = chunk_to_var(b);
1035 if (!two)
1036 goto free;
1038 ret = get_comparison_strings(one, two);
1039 free:
1040 free_string(one);
1041 free_string(two);
1042 return ret;
1045 static void update_links_from_call(struct expression *left,
1046 int left_compare,
1047 struct expression *right)
1049 struct string_list *links;
1050 struct smatch_state *state;
1051 struct compare_data *data;
1052 struct symbol *left_sym, *right_sym;
1053 char *left_var = NULL;
1054 char *right_var = NULL;
1055 struct var_sym_list *left_vsl;
1056 const char *var;
1057 struct var_sym_list *vsl;
1058 int comparison;
1059 char *tmp;
1061 left_var = chunk_to_var_sym(left, &left_sym);
1062 if (!left_var)
1063 goto done;
1064 left_vsl = expr_to_vsl(left);
1065 right_var = chunk_to_var_sym(right, &right_sym);
1066 if (!right_var)
1067 goto done;
1069 state = get_state(link_id, right_var, right_sym);
1070 if (!state)
1071 return;
1072 links = state->data;
1074 FOR_EACH_PTR(links, tmp) {
1075 state = get_state(compare_id, tmp, NULL);
1076 if (!state || !state->data)
1077 continue;
1078 data = state->data;
1079 comparison = data->comparison;
1080 var = data->var2;
1081 vsl = data->vsl2;
1082 if (chunk_vsl_eq(var, vsl, right_var, NULL)) {
1083 var = data->var1;
1084 vsl = data->vsl1;
1085 comparison = flip_op(comparison);
1087 comparison = combine_comparisons(left_compare, comparison);
1088 if (!comparison)
1089 continue;
1090 add_comparison_var_sym(left_var, left_vsl, comparison, var, vsl);
1091 } END_FOR_EACH_PTR(tmp);
1093 done:
1094 free_string(right_var);
1097 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
1099 struct expression *arg;
1100 int comparison;
1101 const char *c = range;
1103 if (!str_to_comparison_arg(c, call, &comparison, &arg))
1104 return;
1105 update_links_from_call(expr, comparison, arg);
1106 add_comparison(expr, comparison, arg);
1109 static char *range_comparison_to_param_helper(struct expression *expr, char starts_with)
1111 struct symbol *param;
1112 char *var = NULL;
1113 char buf[256];
1114 char *ret_str = NULL;
1115 int compare;
1116 int i;
1118 var = chunk_to_var(expr);
1119 if (!var)
1120 goto free;
1122 i = -1;
1123 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1124 i++;
1125 if (!param->ident)
1126 continue;
1127 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1128 compare = get_comparison_strings(var, buf);
1129 if (!compare)
1130 continue;
1131 if (show_special(compare)[0] != starts_with)
1132 continue;
1133 snprintf(buf, sizeof(buf), "[%sp%d]", show_special(compare), i);
1134 ret_str = alloc_sname(buf);
1135 break;
1136 } END_FOR_EACH_PTR(param);
1138 free:
1139 free_string(var);
1140 return ret_str;
1143 char *expr_equal_to_param(struct expression *expr)
1145 return range_comparison_to_param_helper(expr, '=');
1148 char *expr_lte_to_param(struct expression *expr)
1150 return range_comparison_to_param_helper(expr, '<');
1153 static void free_data(struct symbol *sym)
1155 if (__inline_fn)
1156 return;
1157 clear_compare_data_alloc();
1160 void register_comparison(int id)
1162 compare_id = id;
1163 add_hook(&match_compare, CONDITION_HOOK);
1164 add_hook(&match_assign, ASSIGNMENT_HOOK);
1165 add_hook(&save_start_states, AFTER_DEF_HOOK);
1166 add_unmatched_state_hook(compare_id, unmatched_comparison);
1167 add_merge_hook(compare_id, &merge_compare_states);
1168 add_hook(&free_data, AFTER_FUNC_HOOK);
1171 void register_comparison_links(int id)
1173 link_id = id;
1174 add_merge_hook(link_id, &merge_links);
1175 add_modification_hook(link_id, &match_modify);