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.
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
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.
32 #include "smatch_extra.h"
33 #include "smatch_slist.h"
35 static int compare_id
;
40 struct var_sym_list
*vsl1
;
43 struct var_sym_list
*vsl2
;
45 ALLOCATOR(compare_data
, "compare data");
47 static struct symbol
*vsl_to_sym(struct var_sym_list
*vsl
)
53 if (ptr_list_size((struct ptr_list
*)vsl
) != 1)
55 vs
= first_ptr_list((struct ptr_list
*)vsl
);
59 static struct smatch_state
*alloc_compare_state(
60 const char *var1
, struct var_sym_list
*vsl1
,
62 const char *var2
, struct var_sym_list
*vsl2
)
64 struct smatch_state
*state
;
65 struct compare_data
*data
;
67 state
= __alloc_smatch_state(0);
68 state
->name
= alloc_sname(show_special(comparison
));
69 data
= __alloc_compare_data(0);
70 data
->var1
= alloc_sname(var1
);
71 data
->vsl1
= clone_var_sym_list(vsl1
);
72 data
->comparison
= comparison
;
73 data
->var2
= alloc_sname(var2
);
74 data
->vsl2
= clone_var_sym_list(vsl2
);
79 static int state_to_comparison(struct smatch_state
*state
)
81 if (!state
|| !state
->data
)
83 return ((struct compare_data
*)state
->data
)->comparison
;
87 * flip_comparison() reverses the op left and right. So "x >= y" becomes "y <= x".
89 int flip_comparison(int op
)
96 case SPECIAL_UNSIGNED_LT
:
97 return SPECIAL_UNSIGNED_GT
;
100 case SPECIAL_UNSIGNED_LTE
:
101 return SPECIAL_UNSIGNED_GTE
;
103 return SPECIAL_EQUAL
;
104 case SPECIAL_NOTEQUAL
:
105 return SPECIAL_NOTEQUAL
;
108 case SPECIAL_UNSIGNED_GTE
:
109 return SPECIAL_UNSIGNED_LTE
;
112 case SPECIAL_UNSIGNED_GT
:
113 return SPECIAL_UNSIGNED_LT
;
115 sm_msg("internal smatch bug. unhandled comparison %d", op
);
120 int negate_comparison(int op
)
127 case SPECIAL_UNSIGNED_LT
:
128 return SPECIAL_UNSIGNED_GTE
;
131 case SPECIAL_UNSIGNED_LTE
:
132 return SPECIAL_UNSIGNED_GT
;
134 return SPECIAL_NOTEQUAL
;
135 case SPECIAL_NOTEQUAL
:
136 return SPECIAL_EQUAL
;
139 case SPECIAL_UNSIGNED_GTE
:
140 return SPECIAL_UNSIGNED_LT
;
143 case SPECIAL_UNSIGNED_GT
:
144 return SPECIAL_UNSIGNED_LTE
;
146 sm_msg("internal smatch bug. unhandled comparison %d", op
);
151 static int rl_comparison(struct range_list
*left_rl
, struct range_list
*right_rl
)
153 sval_t left_min
, left_max
, right_min
, right_max
;
155 if (!left_rl
|| !right_rl
)
158 left_min
= rl_min(left_rl
);
159 left_max
= rl_max(left_rl
);
160 right_min
= rl_min(right_rl
);
161 right_max
= rl_max(right_rl
);
163 if (left_min
.value
== left_max
.value
&&
164 right_min
.value
== right_max
.value
&&
165 left_min
.value
== right_min
.value
)
166 return SPECIAL_EQUAL
;
168 if (sval_cmp(left_max
, right_min
) < 0)
170 if (sval_cmp(left_max
, right_min
) == 0)
172 if (sval_cmp(left_min
, right_max
) > 0)
174 if (sval_cmp(left_min
, right_max
) == 0)
180 static struct range_list
*get_orig_rl(struct var_sym_list
*vsl
)
183 struct smatch_state
*state
;
187 sym
= vsl_to_sym(vsl
);
188 if (!sym
|| !sym
->ident
)
190 state
= get_orig_estate(sym
->ident
->name
, sym
);
191 return estate_rl(state
);
194 static struct smatch_state
*unmatched_comparison(struct sm_state
*sm
)
196 struct compare_data
*data
= sm
->state
->data
;
197 struct range_list
*left_rl
, *right_rl
;
203 if (strstr(data
->var1
, " orig"))
204 left_rl
= get_orig_rl(data
->vsl1
);
205 else if (!get_implied_rl_var_sym(data
->var1
, vsl_to_sym(data
->vsl1
), &left_rl
))
207 if (strstr(data
->var2
, " orig"))
208 right_rl
= get_orig_rl(data
->vsl2
);
209 else if (!get_implied_rl_var_sym(data
->var2
, vsl_to_sym(data
->vsl2
), &right_rl
))
213 op
= rl_comparison(left_rl
, right_rl
);
215 return alloc_compare_state(data
->var1
, data
->vsl1
, op
, data
->var2
, data
->vsl2
);
220 /* remove_unsigned_from_comparison() is obviously a hack. */
221 static int remove_unsigned_from_comparison(int op
)
224 case SPECIAL_UNSIGNED_LT
:
226 case SPECIAL_UNSIGNED_LTE
:
228 case SPECIAL_UNSIGNED_GTE
:
230 case SPECIAL_UNSIGNED_GT
:
238 * This is for when you merge states "a < b" and "a == b", the result is that
239 * we can say for sure, "a <= b" after the merge.
241 static int merge_comparisons(int one
, int two
)
245 one
= remove_unsigned_from_comparison(one
);
246 two
= remove_unsigned_from_comparison(two
);
293 return SPECIAL_NOTEQUAL
;
304 * This is for if you have "a < b" and "b <= c". Or in other words,
305 * "a < b <= c". You would call this like get_combined_comparison('<', '<=').
306 * The return comparison would be '<'.
308 * This function is different from merge_comparisons(), for example:
309 * merge_comparison('<', '==') returns '<='
310 * get_combined_comparison('<', '==') returns '<'
312 static int combine_comparisons(int left_compare
, int right_compare
)
316 left_compare
= remove_unsigned_from_comparison(left_compare
);
317 right_compare
= remove_unsigned_from_comparison(right_compare
);
321 switch (left_compare
) {
330 return right_compare
;
339 switch (right_compare
) {
371 static int filter_comparison(int orig
, int op
)
383 case SPECIAL_NOTEQUAL
:
393 case SPECIAL_NOTEQUAL
:
402 case SPECIAL_UNSIGNED_LTE
:
403 case SPECIAL_UNSIGNED_GTE
:
404 return SPECIAL_EQUAL
;
407 case SPECIAL_NOTEQUAL
:
412 case SPECIAL_UNSIGNED_LT
:
413 case SPECIAL_UNSIGNED_LTE
:
414 return SPECIAL_UNSIGNED_LT
;
415 case SPECIAL_NOTEQUAL
:
420 case SPECIAL_UNSIGNED_GT
:
421 case SPECIAL_UNSIGNED_GTE
:
422 return SPECIAL_UNSIGNED_GT
;
428 return SPECIAL_EQUAL
;
433 case SPECIAL_NOTEQUAL
:
441 case SPECIAL_NOTEQUAL
:
445 case SPECIAL_UNSIGNED_LT
:
447 case SPECIAL_UNSIGNED_LT
:
448 case SPECIAL_UNSIGNED_LTE
:
449 case SPECIAL_NOTEQUAL
:
450 return SPECIAL_UNSIGNED_LT
;
453 case SPECIAL_UNSIGNED_LTE
:
455 case SPECIAL_UNSIGNED_LT
:
456 case SPECIAL_UNSIGNED_LTE
:
459 case SPECIAL_NOTEQUAL
:
460 return SPECIAL_UNSIGNED_LT
;
461 case SPECIAL_UNSIGNED_GTE
:
462 return SPECIAL_EQUAL
;
465 case SPECIAL_UNSIGNED_GTE
:
467 case SPECIAL_UNSIGNED_LTE
:
468 return SPECIAL_EQUAL
;
469 case SPECIAL_NOTEQUAL
:
470 return SPECIAL_UNSIGNED_GT
;
472 case SPECIAL_UNSIGNED_GTE
:
473 case SPECIAL_UNSIGNED_GT
:
477 case SPECIAL_UNSIGNED_GT
:
479 case SPECIAL_UNSIGNED_GT
:
480 case SPECIAL_UNSIGNED_GTE
:
481 case SPECIAL_NOTEQUAL
:
482 return SPECIAL_UNSIGNED_GT
;
489 static struct smatch_state
*merge_compare_states(struct smatch_state
*s1
, struct smatch_state
*s2
)
491 struct compare_data
*data
= s1
->data
;
494 op
= merge_comparisons(state_to_comparison(s1
), state_to_comparison(s2
));
496 return alloc_compare_state(data
->var1
, data
->vsl1
, op
, data
->var2
, data
->vsl2
);
500 static struct smatch_state
*alloc_link_state(struct string_list
*links
)
502 struct smatch_state
*state
;
503 static char buf
[256];
507 state
= __alloc_smatch_state(0);
510 FOR_EACH_PTR(links
, tmp
) {
512 snprintf(buf
, sizeof(buf
), "%s", tmp
);
514 append(buf
, ", ", sizeof(buf
));
515 append(buf
, tmp
, sizeof(buf
));
517 } END_FOR_EACH_PTR(tmp
);
519 state
->name
= alloc_sname(buf
);
524 static void save_start_states(struct statement
*stmt
)
526 struct symbol
*param
;
528 char state_name
[128];
529 struct smatch_state
*state
;
530 struct string_list
*links
;
533 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
534 struct var_sym_list
*vsl1
= NULL
;
535 struct var_sym_list
*vsl2
= NULL
;
539 snprintf(orig
, sizeof(orig
), "%s orig", param
->ident
->name
);
540 snprintf(state_name
, sizeof(state_name
), "%s vs %s", param
->ident
->name
, orig
);
541 add_var_sym(&vsl1
, param
->ident
->name
, param
);
542 add_var_sym(&vsl2
, orig
, param
);
543 state
= alloc_compare_state(param
->ident
->name
, vsl1
, SPECIAL_EQUAL
, alloc_sname(orig
), vsl2
);
544 set_state(compare_id
, state_name
, NULL
, state
);
546 link
= alloc_sname(state_name
);
548 insert_string(&links
, link
);
549 state
= alloc_link_state(links
);
550 set_state(link_id
, param
->ident
->name
, param
, state
);
551 } END_FOR_EACH_PTR(param
);
554 static struct smatch_state
*merge_links(struct smatch_state
*s1
, struct smatch_state
*s2
)
556 struct smatch_state
*ret
;
557 struct string_list
*links
;
559 links
= combine_string_lists(s1
->data
, s2
->data
);
560 ret
= alloc_link_state(links
);
564 static void save_link_var_sym(const char *var
, struct symbol
*sym
, const char *link
)
566 struct smatch_state
*old_state
, *new_state
;
567 struct string_list
*links
;
570 old_state
= get_state(link_id
, var
, sym
);
572 links
= clone_str_list(old_state
->data
);
576 new = alloc_sname(link
);
577 insert_string(&links
, new);
579 new_state
= alloc_link_state(links
);
580 set_state(link_id
, var
, sym
, new_state
);
583 static void match_inc(struct sm_state
*sm
)
585 struct string_list
*links
;
586 struct smatch_state
*state
;
589 links
= sm
->state
->data
;
591 FOR_EACH_PTR(links
, tmp
) {
592 state
= get_state(compare_id
, tmp
, NULL
);
594 switch (state_to_comparison(state
)) {
597 case SPECIAL_UNSIGNED_GTE
:
599 case SPECIAL_UNSIGNED_GT
: {
600 struct compare_data
*data
= state
->data
;
601 struct smatch_state
*new;
603 new = alloc_compare_state(data
->var1
, data
->vsl1
, '>', data
->var2
, data
->vsl2
);
604 set_state(compare_id
, tmp
, NULL
, new);
608 set_state(compare_id
, tmp
, NULL
, &undefined
);
610 } END_FOR_EACH_PTR(tmp
);
613 static void match_dec(struct sm_state
*sm
)
615 struct string_list
*links
;
616 struct smatch_state
*state
;
619 links
= sm
->state
->data
;
621 FOR_EACH_PTR(links
, tmp
) {
622 state
= get_state(compare_id
, tmp
, NULL
);
624 switch (state_to_comparison(state
)) {
627 case SPECIAL_UNSIGNED_LTE
:
629 case SPECIAL_UNSIGNED_LT
: {
630 struct compare_data
*data
= state
->data
;
631 struct smatch_state
*new;
633 new = alloc_compare_state(data
->var1
, data
->vsl1
, '<', data
->var2
, data
->vsl2
);
634 set_state(compare_id
, tmp
, NULL
, new);
638 set_state(compare_id
, tmp
, NULL
, &undefined
);
640 } END_FOR_EACH_PTR(tmp
);
643 static int match_inc_dec(struct sm_state
*sm
, struct expression
*mod_expr
)
647 if (mod_expr
->type
!= EXPR_PREOP
&& mod_expr
->type
!= EXPR_POSTOP
)
650 if (mod_expr
->op
== SPECIAL_INCREMENT
) {
654 if (mod_expr
->op
== SPECIAL_DECREMENT
) {
661 static void match_modify(struct sm_state
*sm
, struct expression
*mod_expr
)
663 struct string_list
*links
;
666 /* Huh??? This needs a comment! */
667 if (match_inc_dec(sm
, mod_expr
))
670 links
= sm
->state
->data
;
672 FOR_EACH_PTR(links
, tmp
) {
673 set_state(compare_id
, tmp
, NULL
, &undefined
);
674 } END_FOR_EACH_PTR(tmp
);
675 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
678 static char *chunk_to_var_sym(struct expression
*expr
, struct symbol
**sym
)
680 char *name
, *left_name
, *right_name
;
684 expr
= strip_expr(expr
);
690 name
= expr_to_var_sym(expr
, &tmp
);
699 if (expr
->type
!= EXPR_BINOP
)
701 if (expr
->op
!= '-' && expr
->op
!= '+')
704 left_name
= expr_to_var(expr
->left
);
707 right_name
= expr_to_var(expr
->right
);
709 free_string(left_name
);
712 snprintf(buf
, sizeof(buf
), "%s %s %s", left_name
, show_special(expr
->op
), right_name
);
713 free_string(left_name
);
714 free_string(right_name
);
715 return alloc_string(buf
);
718 static char *chunk_to_var(struct expression
*expr
)
720 return chunk_to_var_sym(expr
, NULL
);
723 static void save_link(struct expression
*expr
, char *link
)
728 expr
= strip_expr(expr
);
729 if (expr
->type
== EXPR_BINOP
) {
732 chunk
= chunk_to_var(expr
);
736 save_link(expr
->left
, link
);
737 save_link(expr
->right
, link
);
738 save_link_var_sym(chunk
, NULL
, link
);
742 var
= expr_to_var_sym(expr
, &sym
);
746 save_link_var_sym(var
, sym
, link
);
751 static int get_orig_comparison(struct stree
*pre_stree
, const char *left
, const char *right
)
753 struct smatch_state
*state
;
754 struct compare_data
*data
;
756 char state_name
[256];
758 if (strcmp(left
, right
) > 0) {
759 const char *tmp
= right
;
766 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
767 state
= get_state_stree(pre_stree
, compare_id
, state_name
, NULL
);
768 if (!state
|| !state
->data
)
772 return flip_comparison(data
->comparison
);
773 return data
->comparison
;
778 * The idea here is that we take a comparison "a < b" and then we look at all
779 * the things which "b" is compared against "b < c" and we say that that implies
780 * a relationship "a < c".
782 * The names here about because the comparisons are organized like this
786 static void update_tf_links(struct stree
*pre_stree
,
787 const char *left_var
, struct var_sym_list
*left_vsl
,
788 int left_comparison
, int left_false_comparison
,
789 const char *mid_var
, struct var_sym_list
*mid_vsl
,
790 struct string_list
*links
)
792 struct smatch_state
*state
;
793 struct smatch_state
*true_state
, *false_state
;
794 struct compare_data
*data
;
795 const char *right_var
;
796 struct var_sym_list
*right_vsl
;
798 int right_comparison
;
800 int false_comparison
;
802 char state_name
[256];
805 FOR_EACH_PTR(links
, tmp
) {
806 state
= get_state_stree(pre_stree
, compare_id
, tmp
, NULL
);
807 if (!state
|| !state
->data
)
810 right_comparison
= data
->comparison
;
811 right_var
= data
->var2
;
812 right_vsl
= data
->vsl2
;
813 if (strcmp(mid_var
, right_var
) == 0) {
814 right_var
= data
->var1
;
815 right_vsl
= data
->vsl1
;
816 right_comparison
= flip_comparison(right_comparison
);
818 if (strcmp(left_var
, right_var
) == 0)
821 orig_comparison
= get_orig_comparison(pre_stree
, left_var
, right_var
);
823 true_comparison
= combine_comparisons(left_comparison
, right_comparison
);
824 false_comparison
= combine_comparisons(left_false_comparison
, right_comparison
);
826 true_comparison
= filter_comparison(orig_comparison
, true_comparison
);
827 false_comparison
= filter_comparison(orig_comparison
, false_comparison
);
829 if (strcmp(left_var
, right_var
) > 0) {
830 const char *tmp_var
= left_var
;
831 struct var_sym_list
*tmp_vsl
= left_vsl
;
833 left_var
= right_var
;
834 left_vsl
= right_vsl
;
837 true_comparison
= flip_comparison(true_comparison
);
838 false_comparison
= flip_comparison(false_comparison
);
841 if (!true_comparison
&& !false_comparison
)
845 true_state
= alloc_compare_state(left_var
, left_vsl
, true_comparison
, right_var
, right_vsl
);
848 if (false_comparison
)
849 false_state
= alloc_compare_state(left_var
, left_vsl
, false_comparison
, right_var
, right_vsl
);
853 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_var
, right_var
);
854 set_true_false_states(compare_id
, state_name
, NULL
, true_state
, false_state
);
855 FOR_EACH_PTR(left_vsl
, vs
) {
856 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
857 } END_FOR_EACH_PTR(vs
);
858 FOR_EACH_PTR(right_vsl
, vs
) {
859 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
860 } END_FOR_EACH_PTR(vs
);
861 if (!vsl_to_sym(left_vsl
))
862 save_link_var_sym(left_var
, NULL
, state_name
);
863 if (!vsl_to_sym(right_vsl
))
864 save_link_var_sym(right_var
, NULL
, state_name
);
865 } END_FOR_EACH_PTR(tmp
);
868 static void update_tf_data(struct stree
*pre_stree
,
869 const char *left_name
, struct var_sym_list
*left_vsl
,
870 const char *right_name
, struct var_sym_list
*right_vsl
,
871 int true_comparison
, int false_comparison
)
873 struct smatch_state
*state
;
875 state
= get_state_stree(pre_stree
, link_id
, right_name
, vsl_to_sym(right_vsl
));
877 update_tf_links(pre_stree
, left_name
, left_vsl
, true_comparison
, false_comparison
, right_name
, right_vsl
, state
->data
);
879 state
= get_state_stree(pre_stree
, link_id
, left_name
, vsl_to_sym(left_vsl
));
881 update_tf_links(pre_stree
, right_name
, right_vsl
, flip_comparison(true_comparison
), flip_comparison(false_comparison
), left_name
, left_vsl
, state
->data
);
884 static void match_compare(struct expression
*expr
)
888 struct symbol
*left_sym
, *right_sym
;
889 struct var_sym_list
*left_vsl
, *right_vsl
;
892 struct smatch_state
*true_state
, *false_state
;
893 char state_name
[256];
894 struct stree
*pre_stree
;
896 if (expr
->type
!= EXPR_COMPARE
)
898 left
= chunk_to_var_sym(expr
->left
, &left_sym
);
901 left_vsl
= expr_to_vsl(expr
->left
);
902 right
= chunk_to_var_sym(expr
->right
, &right_sym
);
905 right_vsl
= expr_to_vsl(expr
->right
);
907 if (strcmp(left
, right
) > 0) {
908 struct symbol
*tmp_sym
= left_sym
;
909 char *tmp_name
= left
;
910 struct var_sym_list
*tmp_vsl
= left_vsl
;
913 left_sym
= right_sym
;
914 left_vsl
= right_vsl
;
918 op
= flip_comparison(expr
->op
);
922 false_op
= negate_comparison(op
);
924 orig_comparison
= get_comparison_strings(left
, right
);
925 op
= filter_comparison(orig_comparison
, op
);
926 false_op
= filter_comparison(orig_comparison
, false_op
);
928 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
929 true_state
= alloc_compare_state(left
, left_vsl
, op
, right
, right_vsl
);
930 false_state
= alloc_compare_state(left
, left_vsl
, false_op
, right
, right_vsl
);
932 pre_stree
= clone_stree(__get_cur_stree());
933 update_tf_data(pre_stree
, left
, left_vsl
, right
, right_vsl
, op
, false_op
);
934 free_stree(&pre_stree
);
936 set_true_false_states(compare_id
, state_name
, NULL
, true_state
, false_state
);
937 save_link(expr
->left
, state_name
);
938 save_link(expr
->right
, state_name
);
944 static void add_comparison_var_sym(const char *left_name
,
945 struct var_sym_list
*left_vsl
,
947 const char *right_name
, struct var_sym_list
*right_vsl
)
949 struct smatch_state
*state
;
951 char state_name
[256];
953 if (strcmp(left_name
, right_name
) > 0) {
954 const char *tmp_name
= left_name
;
955 struct var_sym_list
*tmp_vsl
= left_vsl
;
957 left_name
= right_name
;
958 left_vsl
= right_vsl
;
959 right_name
= tmp_name
;
961 comparison
= flip_comparison(comparison
);
963 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_name
, right_name
);
964 state
= alloc_compare_state(left_name
, left_vsl
, comparison
, right_name
, right_vsl
);
966 set_state(compare_id
, state_name
, NULL
, state
);
968 FOR_EACH_PTR(left_vsl
, vs
) {
969 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
970 } END_FOR_EACH_PTR(vs
);
971 FOR_EACH_PTR(right_vsl
, vs
) {
972 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
973 } END_FOR_EACH_PTR(vs
);
976 static void add_comparison(struct expression
*left
, int comparison
, struct expression
*right
)
978 char *left_name
= NULL
;
979 char *right_name
= NULL
;
980 struct symbol
*left_sym
, *right_sym
;
981 struct var_sym_list
*left_vsl
, *right_vsl
;
982 struct smatch_state
*state
;
983 char state_name
[256];
985 left_name
= chunk_to_var_sym(left
, &left_sym
);
988 left_vsl
= expr_to_vsl(left
);
989 right_name
= chunk_to_var_sym(right
, &right_sym
);
992 right_vsl
= expr_to_vsl(right
);
994 if (strcmp(left_name
, right_name
) > 0) {
995 struct symbol
*tmp_sym
= left_sym
;
996 char *tmp_name
= left_name
;
997 struct var_sym_list
*tmp_vsl
= left_vsl
;
999 left_name
= right_name
;
1000 left_sym
= right_sym
;
1001 left_vsl
= right_vsl
;
1002 right_name
= tmp_name
;
1003 right_sym
= tmp_sym
;
1004 right_vsl
= tmp_vsl
;
1005 comparison
= flip_comparison(comparison
);
1007 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_name
, right_name
);
1008 state
= alloc_compare_state(left_name
, left_vsl
, comparison
, right_name
, right_vsl
);
1010 set_state(compare_id
, state_name
, NULL
, state
);
1011 save_link(left
, state_name
);
1012 save_link(right
, state_name
);
1015 free_string(left_name
);
1016 free_string(right_name
);
1019 static void match_assign_add(struct expression
*expr
)
1021 struct expression
*right
;
1022 struct expression
*r_left
, *r_right
;
1023 sval_t left_tmp
, right_tmp
;
1025 right
= strip_expr(expr
->right
);
1026 r_left
= strip_expr(right
->left
);
1027 r_right
= strip_expr(right
->right
);
1029 get_absolute_min(r_left
, &left_tmp
);
1030 get_absolute_min(r_right
, &right_tmp
);
1032 if (left_tmp
.value
> 0)
1033 add_comparison(expr
->left
, '>', r_right
);
1034 else if (left_tmp
.value
== 0)
1035 add_comparison(expr
->left
, SPECIAL_GTE
, r_right
);
1037 if (right_tmp
.value
> 0)
1038 add_comparison(expr
->left
, '>', r_left
);
1039 else if (right_tmp
.value
== 0)
1040 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
1043 static void match_assign_sub(struct expression
*expr
)
1045 struct expression
*right
;
1046 struct expression
*r_left
, *r_right
;
1050 right
= strip_expr(expr
->right
);
1051 r_left
= strip_expr(right
->left
);
1052 r_right
= strip_expr(right
->right
);
1054 if (get_absolute_min(r_right
, &min
) && sval_is_negative(min
))
1057 comparison
= get_comparison(r_left
, r_right
);
1059 switch (comparison
) {
1062 if (implied_not_equal(r_right
, 0))
1063 add_comparison(expr
->left
, '>', r_left
);
1065 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
1070 static void match_assign_divide(struct expression
*expr
)
1072 struct expression
*right
;
1073 struct expression
*r_left
, *r_right
;
1076 right
= strip_expr(expr
->right
);
1077 r_left
= strip_expr(right
->left
);
1078 r_right
= strip_expr(right
->right
);
1079 if (!get_implied_min(r_right
, &min
) || min
.value
<= 1)
1082 add_comparison(expr
->left
, '<', r_left
);
1085 static void match_binop_assign(struct expression
*expr
)
1087 struct expression
*right
;
1089 right
= strip_expr(expr
->right
);
1090 if (right
->op
== '+')
1091 match_assign_add(expr
);
1092 if (right
->op
== '-')
1093 match_assign_sub(expr
);
1094 if (right
->op
== '/')
1095 match_assign_divide(expr
);
1098 static void copy_comparisons(struct expression
*left
, struct expression
*right
)
1100 struct string_list
*links
;
1101 struct smatch_state
*state
;
1102 struct compare_data
*data
;
1103 struct symbol
*left_sym
, *right_sym
;
1104 char *left_var
= NULL
;
1105 char *right_var
= NULL
;
1106 struct var_sym_list
*left_vsl
;
1108 struct var_sym_list
*vsl
;
1112 left_var
= chunk_to_var_sym(left
, &left_sym
);
1115 left_vsl
= expr_to_vsl(left
);
1116 right_var
= chunk_to_var_sym(right
, &right_sym
);
1120 state
= get_state(link_id
, right_var
, right_sym
);
1123 links
= state
->data
;
1125 FOR_EACH_PTR(links
, tmp
) {
1126 state
= get_state(compare_id
, tmp
, NULL
);
1127 if (!state
|| !state
->data
)
1130 comparison
= data
->comparison
;
1133 if (strcmp(var
, right_var
) == 0) {
1136 comparison
= flip_comparison(comparison
);
1138 add_comparison_var_sym(left_var
, left_vsl
, comparison
, var
, vsl
);
1139 } END_FOR_EACH_PTR(tmp
);
1142 free_string(right_var
);
1145 static void match_assign(struct expression
*expr
)
1147 struct expression
*right
;
1149 if (expr
->op
!= '=')
1152 if (is_struct(expr
->left
))
1155 copy_comparisons(expr
->left
, expr
->right
);
1156 add_comparison(expr
->left
, SPECIAL_EQUAL
, expr
->right
);
1158 right
= strip_expr(expr
->right
);
1159 if (right
->type
== EXPR_BINOP
)
1160 match_binop_assign(expr
);
1163 int get_comparison_strings(const char *one
, const char *two
)
1166 struct smatch_state
*state
;
1170 if (strcmp(one
, two
) == 0)
1171 return SPECIAL_EQUAL
;
1173 if (strcmp(one
, two
) > 0) {
1174 const char *tmp
= one
;
1181 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
1182 state
= get_state(compare_id
, buf
, NULL
);
1184 ret
= state_to_comparison(state
);
1187 ret
= flip_comparison(ret
);
1192 int get_comparison(struct expression
*a
, struct expression
*b
)
1198 one
= chunk_to_var(a
);
1201 two
= chunk_to_var(b
);
1205 ret
= get_comparison_strings(one
, two
);
1212 int possible_comparison(struct expression
*a
, int comparison
, struct expression
*b
)
1218 struct sm_state
*sm
;
1221 one
= chunk_to_var(a
);
1224 two
= chunk_to_var(b
);
1229 if (strcmp(one
, two
) == 0 && comparison
== SPECIAL_EQUAL
) {
1234 if (strcmp(one
, two
) > 0) {
1239 comparison
= flip_comparison(comparison
);
1242 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
1243 sm
= get_sm_state(compare_id
, buf
, NULL
);
1247 FOR_EACH_PTR(sm
->possible
, sm
) {
1248 if (!sm
->state
->data
)
1250 saved
= ((struct compare_data
*)sm
->state
->data
)->comparison
;
1251 if (saved
== comparison
)
1253 if (comparison
== SPECIAL_EQUAL
&&
1254 (saved
== SPECIAL_LTE
||
1255 saved
== SPECIAL_GTE
||
1256 saved
== SPECIAL_UNSIGNED_LTE
||
1257 saved
== SPECIAL_UNSIGNED_GTE
))
1261 } END_FOR_EACH_PTR(sm
);
1270 static void update_links_from_call(struct expression
*left
,
1272 struct expression
*right
)
1274 struct string_list
*links
;
1275 struct smatch_state
*state
;
1276 struct compare_data
*data
;
1277 struct symbol
*left_sym
, *right_sym
;
1278 char *left_var
= NULL
;
1279 char *right_var
= NULL
;
1280 struct var_sym_list
*left_vsl
;
1282 struct var_sym_list
*vsl
;
1286 left_var
= chunk_to_var_sym(left
, &left_sym
);
1289 left_vsl
= expr_to_vsl(left
);
1290 right_var
= chunk_to_var_sym(right
, &right_sym
);
1294 state
= get_state(link_id
, right_var
, right_sym
);
1297 links
= state
->data
;
1299 FOR_EACH_PTR(links
, tmp
) {
1300 state
= get_state(compare_id
, tmp
, NULL
);
1301 if (!state
|| !state
->data
)
1304 comparison
= data
->comparison
;
1307 if (strcmp(var
, right_var
) == 0) {
1310 comparison
= flip_comparison(comparison
);
1312 comparison
= combine_comparisons(left_compare
, comparison
);
1315 add_comparison_var_sym(left_var
, left_vsl
, comparison
, var
, vsl
);
1316 } END_FOR_EACH_PTR(tmp
);
1319 free_string(right_var
);
1322 void __add_comparison_info(struct expression
*expr
, struct expression
*call
, const char *range
)
1324 struct expression
*arg
;
1326 const char *c
= range
;
1328 if (!str_to_comparison_arg(c
, call
, &comparison
, &arg
))
1330 update_links_from_call(expr
, comparison
, arg
);
1331 add_comparison(expr
, comparison
, arg
);
1334 static char *range_comparison_to_param_helper(struct expression
*expr
, char starts_with
, int ignore
)
1336 struct symbol
*param
;
1339 char *ret_str
= NULL
;
1343 var
= chunk_to_var(expr
);
1348 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
1354 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
1355 compare
= get_comparison_strings(var
, buf
);
1358 if (show_special(compare
)[0] != starts_with
)
1360 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_special(compare
), i
);
1361 ret_str
= alloc_sname(buf
);
1363 } END_FOR_EACH_PTR(param
);
1370 char *expr_equal_to_param(struct expression
*expr
, int ignore
)
1372 return range_comparison_to_param_helper(expr
, '=', ignore
);
1375 char *expr_lte_to_param(struct expression
*expr
, int ignore
)
1377 return range_comparison_to_param_helper(expr
, '<', ignore
);
1380 char *expr_param_comparison(struct expression
*expr
, int ignore
)
1382 struct symbol
*param
;
1385 char *ret_str
= NULL
;
1389 var
= chunk_to_var(expr
);
1394 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
1400 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
1401 compare
= get_comparison_strings(var
, buf
);
1404 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_special(compare
), i
);
1405 ret_str
= alloc_sname(buf
);
1407 } END_FOR_EACH_PTR(param
);
1414 static void free_data(struct symbol
*sym
)
1418 clear_compare_data_alloc();
1421 void register_comparison(int id
)
1424 add_hook(&match_compare
, CONDITION_HOOK
);
1425 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
1426 add_hook(&save_start_states
, AFTER_DEF_HOOK
);
1427 add_unmatched_state_hook(compare_id
, unmatched_comparison
);
1428 add_merge_hook(compare_id
, &merge_compare_states
);
1429 add_hook(&free_data
, AFTER_FUNC_HOOK
);
1432 void register_comparison_links(int id
)
1435 add_merge_hook(link_id
, &merge_links
);
1436 add_modification_hook(link_id
, &match_modify
);