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
;
38 ALLOCATOR(compare_data
, "compare data");
40 static struct symbol
*vsl_to_sym(struct var_sym_list
*vsl
)
46 if (ptr_list_size((struct ptr_list
*)vsl
) != 1)
48 vs
= first_ptr_list((struct ptr_list
*)vsl
);
52 static struct smatch_state
*alloc_compare_state(
53 const char *var1
, struct var_sym_list
*vsl1
,
55 const char *var2
, struct var_sym_list
*vsl2
)
57 struct smatch_state
*state
;
58 struct compare_data
*data
;
60 state
= __alloc_smatch_state(0);
61 state
->name
= alloc_sname(show_special(comparison
));
62 data
= __alloc_compare_data(0);
63 data
->var1
= alloc_sname(var1
);
64 data
->vsl1
= clone_var_sym_list(vsl1
);
65 data
->comparison
= comparison
;
66 data
->var2
= alloc_sname(var2
);
67 data
->vsl2
= clone_var_sym_list(vsl2
);
72 static int state_to_comparison(struct smatch_state
*state
)
74 if (!state
|| !state
->data
)
76 return ((struct compare_data
*)state
->data
)->comparison
;
80 * flip_comparison() reverses the op left and right. So "x >= y" becomes "y <= x".
82 int flip_comparison(int op
)
89 case SPECIAL_UNSIGNED_LT
:
90 return SPECIAL_UNSIGNED_GT
;
93 case SPECIAL_UNSIGNED_LTE
:
94 return SPECIAL_UNSIGNED_GTE
;
97 case SPECIAL_NOTEQUAL
:
98 return SPECIAL_NOTEQUAL
;
101 case SPECIAL_UNSIGNED_GTE
:
102 return SPECIAL_UNSIGNED_LTE
;
105 case SPECIAL_UNSIGNED_GT
:
106 return SPECIAL_UNSIGNED_LT
;
108 sm_msg("internal smatch bug. unhandled comparison %d", op
);
113 int negate_comparison(int op
)
120 case SPECIAL_UNSIGNED_LT
:
121 return SPECIAL_UNSIGNED_GTE
;
124 case SPECIAL_UNSIGNED_LTE
:
125 return SPECIAL_UNSIGNED_GT
;
127 return SPECIAL_NOTEQUAL
;
128 case SPECIAL_NOTEQUAL
:
129 return SPECIAL_EQUAL
;
132 case SPECIAL_UNSIGNED_GTE
:
133 return SPECIAL_UNSIGNED_LT
;
136 case SPECIAL_UNSIGNED_GT
:
137 return SPECIAL_UNSIGNED_LTE
;
139 sm_msg("internal smatch bug. unhandled comparison %d", op
);
144 static int rl_comparison(struct range_list
*left_rl
, struct range_list
*right_rl
)
146 sval_t left_min
, left_max
, right_min
, right_max
;
148 if (!left_rl
|| !right_rl
)
151 left_min
= rl_min(left_rl
);
152 left_max
= rl_max(left_rl
);
153 right_min
= rl_min(right_rl
);
154 right_max
= rl_max(right_rl
);
156 if (left_min
.value
== left_max
.value
&&
157 right_min
.value
== right_max
.value
&&
158 left_min
.value
== right_min
.value
)
159 return SPECIAL_EQUAL
;
161 if (sval_cmp(left_max
, right_min
) < 0)
163 if (sval_cmp(left_max
, right_min
) == 0)
165 if (sval_cmp(left_min
, right_max
) > 0)
167 if (sval_cmp(left_min
, right_max
) == 0)
173 static struct range_list
*get_orig_rl(struct var_sym_list
*vsl
)
176 struct smatch_state
*state
;
180 sym
= vsl_to_sym(vsl
);
181 if (!sym
|| !sym
->ident
)
183 state
= get_orig_estate(sym
->ident
->name
, sym
);
184 return estate_rl(state
);
187 static struct smatch_state
*unmatched_comparison(struct sm_state
*sm
)
189 struct compare_data
*data
= sm
->state
->data
;
190 struct range_list
*left_rl
, *right_rl
;
196 if (strstr(data
->var1
, " orig"))
197 left_rl
= get_orig_rl(data
->vsl1
);
198 else if (!get_implied_rl_var_sym(data
->var1
, vsl_to_sym(data
->vsl1
), &left_rl
))
200 if (strstr(data
->var2
, " orig"))
201 right_rl
= get_orig_rl(data
->vsl2
);
202 else if (!get_implied_rl_var_sym(data
->var2
, vsl_to_sym(data
->vsl2
), &right_rl
))
206 op
= rl_comparison(left_rl
, right_rl
);
208 return alloc_compare_state(data
->var1
, data
->vsl1
, op
, data
->var2
, data
->vsl2
);
213 /* remove_unsigned_from_comparison() is obviously a hack. */
214 static int remove_unsigned_from_comparison(int op
)
217 case SPECIAL_UNSIGNED_LT
:
219 case SPECIAL_UNSIGNED_LTE
:
221 case SPECIAL_UNSIGNED_GTE
:
223 case SPECIAL_UNSIGNED_GT
:
231 * This is for when you merge states "a < b" and "a == b", the result is that
232 * we can say for sure, "a <= b" after the merge.
234 static int merge_comparisons(int one
, int two
)
238 one
= remove_unsigned_from_comparison(one
);
239 two
= remove_unsigned_from_comparison(two
);
286 return SPECIAL_NOTEQUAL
;
297 * This is for if you have "a < b" and "b <= c". Or in other words,
298 * "a < b <= c". You would call this like get_combined_comparison('<', '<=').
299 * The return comparison would be '<'.
301 * This function is different from merge_comparisons(), for example:
302 * merge_comparison('<', '==') returns '<='
303 * get_combined_comparison('<', '==') returns '<'
305 static int combine_comparisons(int left_compare
, int right_compare
)
309 left_compare
= remove_unsigned_from_comparison(left_compare
);
310 right_compare
= remove_unsigned_from_comparison(right_compare
);
314 switch (left_compare
) {
323 return right_compare
;
332 switch (right_compare
) {
364 static int filter_comparison(int orig
, int op
)
376 case SPECIAL_NOTEQUAL
:
386 case SPECIAL_NOTEQUAL
:
395 case SPECIAL_UNSIGNED_LTE
:
396 case SPECIAL_UNSIGNED_GTE
:
397 return SPECIAL_EQUAL
;
400 case SPECIAL_NOTEQUAL
:
405 case SPECIAL_UNSIGNED_LT
:
406 case SPECIAL_UNSIGNED_LTE
:
407 return SPECIAL_UNSIGNED_LT
;
408 case SPECIAL_NOTEQUAL
:
413 case SPECIAL_UNSIGNED_GT
:
414 case SPECIAL_UNSIGNED_GTE
:
415 return SPECIAL_UNSIGNED_GT
;
421 return SPECIAL_EQUAL
;
426 case SPECIAL_NOTEQUAL
:
434 case SPECIAL_NOTEQUAL
:
438 case SPECIAL_UNSIGNED_LT
:
440 case SPECIAL_UNSIGNED_LT
:
441 case SPECIAL_UNSIGNED_LTE
:
442 case SPECIAL_NOTEQUAL
:
443 return SPECIAL_UNSIGNED_LT
;
446 case SPECIAL_UNSIGNED_LTE
:
448 case SPECIAL_UNSIGNED_LT
:
449 case SPECIAL_UNSIGNED_LTE
:
452 case SPECIAL_NOTEQUAL
:
453 return SPECIAL_UNSIGNED_LT
;
454 case SPECIAL_UNSIGNED_GTE
:
455 return SPECIAL_EQUAL
;
458 case SPECIAL_UNSIGNED_GTE
:
460 case SPECIAL_UNSIGNED_LTE
:
461 return SPECIAL_EQUAL
;
462 case SPECIAL_NOTEQUAL
:
463 return SPECIAL_UNSIGNED_GT
;
465 case SPECIAL_UNSIGNED_GTE
:
466 case SPECIAL_UNSIGNED_GT
:
470 case SPECIAL_UNSIGNED_GT
:
472 case SPECIAL_UNSIGNED_GT
:
473 case SPECIAL_UNSIGNED_GTE
:
474 case SPECIAL_NOTEQUAL
:
475 return SPECIAL_UNSIGNED_GT
;
482 static struct smatch_state
*merge_compare_states(struct smatch_state
*s1
, struct smatch_state
*s2
)
484 struct compare_data
*data
= s1
->data
;
487 op
= merge_comparisons(state_to_comparison(s1
), state_to_comparison(s2
));
489 return alloc_compare_state(data
->var1
, data
->vsl1
, op
, data
->var2
, data
->vsl2
);
493 static struct smatch_state
*alloc_link_state(struct string_list
*links
)
495 struct smatch_state
*state
;
496 static char buf
[256];
500 state
= __alloc_smatch_state(0);
503 FOR_EACH_PTR(links
, tmp
) {
505 snprintf(buf
, sizeof(buf
), "%s", tmp
);
507 append(buf
, ", ", sizeof(buf
));
508 append(buf
, tmp
, sizeof(buf
));
510 } END_FOR_EACH_PTR(tmp
);
512 state
->name
= alloc_sname(buf
);
517 static void save_start_states(struct statement
*stmt
)
519 struct symbol
*param
;
521 char state_name
[128];
522 struct smatch_state
*state
;
523 struct string_list
*links
;
526 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
527 struct var_sym_list
*vsl1
= NULL
;
528 struct var_sym_list
*vsl2
= NULL
;
532 snprintf(orig
, sizeof(orig
), "%s orig", param
->ident
->name
);
533 snprintf(state_name
, sizeof(state_name
), "%s vs %s", param
->ident
->name
, orig
);
534 add_var_sym(&vsl1
, param
->ident
->name
, param
);
535 add_var_sym(&vsl2
, orig
, param
);
536 state
= alloc_compare_state(param
->ident
->name
, vsl1
, SPECIAL_EQUAL
, alloc_sname(orig
), vsl2
);
537 set_state(compare_id
, state_name
, NULL
, state
);
539 link
= alloc_sname(state_name
);
541 insert_string(&links
, link
);
542 state
= alloc_link_state(links
);
543 set_state(link_id
, param
->ident
->name
, param
, state
);
544 } END_FOR_EACH_PTR(param
);
547 static struct smatch_state
*merge_links(struct smatch_state
*s1
, struct smatch_state
*s2
)
549 struct smatch_state
*ret
;
550 struct string_list
*links
;
552 links
= combine_string_lists(s1
->data
, s2
->data
);
553 ret
= alloc_link_state(links
);
557 static void save_link_var_sym(const char *var
, struct symbol
*sym
, const char *link
)
559 struct smatch_state
*old_state
, *new_state
;
560 struct string_list
*links
;
563 old_state
= get_state(link_id
, var
, sym
);
565 links
= clone_str_list(old_state
->data
);
569 new = alloc_sname(link
);
570 insert_string(&links
, new);
572 new_state
= alloc_link_state(links
);
573 set_state(link_id
, var
, sym
, new_state
);
576 static void match_inc(struct sm_state
*sm
)
578 struct string_list
*links
;
579 struct smatch_state
*state
;
582 links
= sm
->state
->data
;
584 FOR_EACH_PTR(links
, tmp
) {
585 state
= get_state(compare_id
, tmp
, NULL
);
587 switch (state_to_comparison(state
)) {
590 case SPECIAL_UNSIGNED_GTE
:
592 case SPECIAL_UNSIGNED_GT
: {
593 struct compare_data
*data
= state
->data
;
594 struct smatch_state
*new;
596 new = alloc_compare_state(data
->var1
, data
->vsl1
, '>', data
->var2
, data
->vsl2
);
597 set_state(compare_id
, tmp
, NULL
, new);
601 set_state(compare_id
, tmp
, NULL
, &undefined
);
603 } END_FOR_EACH_PTR(tmp
);
606 static void match_dec(struct sm_state
*sm
)
608 struct string_list
*links
;
609 struct smatch_state
*state
;
612 links
= sm
->state
->data
;
614 FOR_EACH_PTR(links
, tmp
) {
615 state
= get_state(compare_id
, tmp
, NULL
);
617 switch (state_to_comparison(state
)) {
620 case SPECIAL_UNSIGNED_LTE
:
622 case SPECIAL_UNSIGNED_LT
: {
623 struct compare_data
*data
= state
->data
;
624 struct smatch_state
*new;
626 new = alloc_compare_state(data
->var1
, data
->vsl1
, '<', data
->var2
, data
->vsl2
);
627 set_state(compare_id
, tmp
, NULL
, new);
631 set_state(compare_id
, tmp
, NULL
, &undefined
);
633 } END_FOR_EACH_PTR(tmp
);
636 static int match_inc_dec(struct sm_state
*sm
, struct expression
*mod_expr
)
640 if (mod_expr
->type
!= EXPR_PREOP
&& mod_expr
->type
!= EXPR_POSTOP
)
643 if (mod_expr
->op
== SPECIAL_INCREMENT
) {
647 if (mod_expr
->op
== SPECIAL_DECREMENT
) {
654 static void match_modify(struct sm_state
*sm
, struct expression
*mod_expr
)
656 struct string_list
*links
;
659 /* Huh??? This needs a comment! */
660 if (match_inc_dec(sm
, mod_expr
))
663 links
= sm
->state
->data
;
665 FOR_EACH_PTR(links
, tmp
) {
666 set_state(compare_id
, tmp
, NULL
, &undefined
);
667 } END_FOR_EACH_PTR(tmp
);
668 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
671 static char *chunk_to_var_sym(struct expression
*expr
, struct symbol
**sym
)
673 char *name
, *left_name
, *right_name
;
677 expr
= strip_expr(expr
);
683 name
= expr_to_var_sym(expr
, &tmp
);
692 if (expr
->type
!= EXPR_BINOP
)
694 if (expr
->op
!= '-' && expr
->op
!= '+')
697 left_name
= expr_to_var(expr
->left
);
700 right_name
= expr_to_var(expr
->right
);
702 free_string(left_name
);
705 snprintf(buf
, sizeof(buf
), "%s %s %s", left_name
, show_special(expr
->op
), right_name
);
706 free_string(left_name
);
707 free_string(right_name
);
708 return alloc_string(buf
);
711 static char *chunk_to_var(struct expression
*expr
)
713 return chunk_to_var_sym(expr
, NULL
);
716 static void save_link(struct expression
*expr
, char *link
)
721 expr
= strip_expr(expr
);
722 if (expr
->type
== EXPR_BINOP
) {
725 chunk
= chunk_to_var(expr
);
729 save_link(expr
->left
, link
);
730 save_link(expr
->right
, link
);
731 save_link_var_sym(chunk
, NULL
, link
);
735 var
= expr_to_var_sym(expr
, &sym
);
739 save_link_var_sym(var
, sym
, link
);
744 static int get_orig_comparison(struct stree
*pre_stree
, const char *left
, const char *right
)
746 struct smatch_state
*state
;
747 struct compare_data
*data
;
749 char state_name
[256];
751 if (strcmp(left
, right
) > 0) {
752 const char *tmp
= right
;
759 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
760 state
= get_state_stree(pre_stree
, compare_id
, state_name
, NULL
);
761 if (!state
|| !state
->data
)
765 return flip_comparison(data
->comparison
);
766 return data
->comparison
;
771 * The idea here is that we take a comparison "a < b" and then we look at all
772 * the things which "b" is compared against "b < c" and we say that that implies
773 * a relationship "a < c".
775 * The names here about because the comparisons are organized like this
779 static void update_tf_links(struct stree
*pre_stree
,
780 const char *left_var
, struct var_sym_list
*left_vsl
,
781 int left_comparison
, int left_false_comparison
,
782 const char *mid_var
, struct var_sym_list
*mid_vsl
,
783 struct string_list
*links
)
785 struct smatch_state
*state
;
786 struct smatch_state
*true_state
, *false_state
;
787 struct compare_data
*data
;
788 const char *right_var
;
789 struct var_sym_list
*right_vsl
;
791 int right_comparison
;
793 int false_comparison
;
795 char state_name
[256];
798 FOR_EACH_PTR(links
, tmp
) {
799 state
= get_state_stree(pre_stree
, compare_id
, tmp
, NULL
);
800 if (!state
|| !state
->data
)
803 right_comparison
= data
->comparison
;
804 right_var
= data
->var2
;
805 right_vsl
= data
->vsl2
;
806 if (strcmp(mid_var
, right_var
) == 0) {
807 right_var
= data
->var1
;
808 right_vsl
= data
->vsl1
;
809 right_comparison
= flip_comparison(right_comparison
);
811 if (strcmp(left_var
, right_var
) == 0)
814 orig_comparison
= get_orig_comparison(pre_stree
, left_var
, right_var
);
816 true_comparison
= combine_comparisons(left_comparison
, right_comparison
);
817 false_comparison
= combine_comparisons(left_false_comparison
, right_comparison
);
819 true_comparison
= filter_comparison(orig_comparison
, true_comparison
);
820 false_comparison
= filter_comparison(orig_comparison
, false_comparison
);
822 if (strcmp(left_var
, right_var
) > 0) {
823 const char *tmp_var
= left_var
;
824 struct var_sym_list
*tmp_vsl
= left_vsl
;
826 left_var
= right_var
;
827 left_vsl
= right_vsl
;
830 true_comparison
= flip_comparison(true_comparison
);
831 false_comparison
= flip_comparison(false_comparison
);
834 if (!true_comparison
&& !false_comparison
)
838 true_state
= alloc_compare_state(left_var
, left_vsl
, true_comparison
, right_var
, right_vsl
);
841 if (false_comparison
)
842 false_state
= alloc_compare_state(left_var
, left_vsl
, false_comparison
, right_var
, right_vsl
);
846 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_var
, right_var
);
847 set_true_false_states(compare_id
, state_name
, NULL
, true_state
, false_state
);
848 FOR_EACH_PTR(left_vsl
, vs
) {
849 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
850 } END_FOR_EACH_PTR(vs
);
851 FOR_EACH_PTR(right_vsl
, vs
) {
852 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
853 } END_FOR_EACH_PTR(vs
);
854 if (!vsl_to_sym(left_vsl
))
855 save_link_var_sym(left_var
, NULL
, state_name
);
856 if (!vsl_to_sym(right_vsl
))
857 save_link_var_sym(right_var
, NULL
, state_name
);
858 } END_FOR_EACH_PTR(tmp
);
861 static void update_tf_data(struct stree
*pre_stree
,
862 const char *left_name
, struct var_sym_list
*left_vsl
,
863 const char *right_name
, struct var_sym_list
*right_vsl
,
864 int true_comparison
, int false_comparison
)
866 struct smatch_state
*state
;
868 state
= get_state_stree(pre_stree
, link_id
, right_name
, vsl_to_sym(right_vsl
));
870 update_tf_links(pre_stree
, left_name
, left_vsl
, true_comparison
, false_comparison
, right_name
, right_vsl
, state
->data
);
872 state
= get_state_stree(pre_stree
, link_id
, left_name
, vsl_to_sym(left_vsl
));
874 update_tf_links(pre_stree
, right_name
, right_vsl
, flip_comparison(true_comparison
), flip_comparison(false_comparison
), left_name
, left_vsl
, state
->data
);
877 static void match_compare(struct expression
*expr
)
881 struct symbol
*left_sym
, *right_sym
;
882 struct var_sym_list
*left_vsl
, *right_vsl
;
885 struct smatch_state
*true_state
, *false_state
;
886 char state_name
[256];
887 struct stree
*pre_stree
;
889 if (expr
->type
!= EXPR_COMPARE
)
891 left
= chunk_to_var_sym(expr
->left
, &left_sym
);
894 left_vsl
= expr_to_vsl(expr
->left
);
895 right
= chunk_to_var_sym(expr
->right
, &right_sym
);
898 right_vsl
= expr_to_vsl(expr
->right
);
900 if (strcmp(left
, right
) > 0) {
901 struct symbol
*tmp_sym
= left_sym
;
902 char *tmp_name
= left
;
903 struct var_sym_list
*tmp_vsl
= left_vsl
;
906 left_sym
= right_sym
;
907 left_vsl
= right_vsl
;
911 op
= flip_comparison(expr
->op
);
915 false_op
= negate_comparison(op
);
917 orig_comparison
= get_comparison_strings(left
, right
);
918 op
= filter_comparison(orig_comparison
, op
);
919 false_op
= filter_comparison(orig_comparison
, false_op
);
921 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
922 true_state
= alloc_compare_state(left
, left_vsl
, op
, right
, right_vsl
);
923 false_state
= alloc_compare_state(left
, left_vsl
, false_op
, right
, right_vsl
);
925 pre_stree
= clone_stree(__get_cur_stree());
926 update_tf_data(pre_stree
, left
, left_vsl
, right
, right_vsl
, op
, false_op
);
927 free_stree(&pre_stree
);
929 set_true_false_states(compare_id
, state_name
, NULL
, true_state
, false_state
);
930 save_link(expr
->left
, state_name
);
931 save_link(expr
->right
, state_name
);
937 static void add_comparison_var_sym(const char *left_name
,
938 struct var_sym_list
*left_vsl
,
940 const char *right_name
, struct var_sym_list
*right_vsl
)
942 struct smatch_state
*state
;
944 char state_name
[256];
946 if (strcmp(left_name
, right_name
) > 0) {
947 const char *tmp_name
= left_name
;
948 struct var_sym_list
*tmp_vsl
= left_vsl
;
950 left_name
= right_name
;
951 left_vsl
= right_vsl
;
952 right_name
= tmp_name
;
954 comparison
= flip_comparison(comparison
);
956 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_name
, right_name
);
957 state
= alloc_compare_state(left_name
, left_vsl
, comparison
, right_name
, right_vsl
);
959 set_state(compare_id
, state_name
, NULL
, state
);
961 FOR_EACH_PTR(left_vsl
, vs
) {
962 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
963 } END_FOR_EACH_PTR(vs
);
964 FOR_EACH_PTR(right_vsl
, vs
) {
965 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
966 } END_FOR_EACH_PTR(vs
);
969 static void add_comparison(struct expression
*left
, int comparison
, struct expression
*right
)
971 char *left_name
= NULL
;
972 char *right_name
= NULL
;
973 struct symbol
*left_sym
, *right_sym
;
974 struct var_sym_list
*left_vsl
, *right_vsl
;
975 struct smatch_state
*state
;
976 char state_name
[256];
978 left_name
= chunk_to_var_sym(left
, &left_sym
);
981 left_vsl
= expr_to_vsl(left
);
982 right_name
= chunk_to_var_sym(right
, &right_sym
);
985 right_vsl
= expr_to_vsl(right
);
987 if (strcmp(left_name
, right_name
) > 0) {
988 struct symbol
*tmp_sym
= left_sym
;
989 char *tmp_name
= left_name
;
990 struct var_sym_list
*tmp_vsl
= left_vsl
;
992 left_name
= right_name
;
993 left_sym
= right_sym
;
994 left_vsl
= right_vsl
;
995 right_name
= tmp_name
;
998 comparison
= flip_comparison(comparison
);
1000 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_name
, right_name
);
1001 state
= alloc_compare_state(left_name
, left_vsl
, comparison
, right_name
, right_vsl
);
1003 set_state(compare_id
, state_name
, NULL
, state
);
1004 save_link(left
, state_name
);
1005 save_link(right
, state_name
);
1008 free_string(left_name
);
1009 free_string(right_name
);
1012 static void match_assign_add(struct expression
*expr
)
1014 struct expression
*right
;
1015 struct expression
*r_left
, *r_right
;
1016 sval_t left_tmp
, right_tmp
;
1018 right
= strip_expr(expr
->right
);
1019 r_left
= strip_expr(right
->left
);
1020 r_right
= strip_expr(right
->right
);
1022 get_absolute_min(r_left
, &left_tmp
);
1023 get_absolute_min(r_right
, &right_tmp
);
1025 if (left_tmp
.value
> 0)
1026 add_comparison(expr
->left
, '>', r_right
);
1027 else if (left_tmp
.value
== 0)
1028 add_comparison(expr
->left
, SPECIAL_GTE
, r_right
);
1030 if (right_tmp
.value
> 0)
1031 add_comparison(expr
->left
, '>', r_left
);
1032 else if (right_tmp
.value
== 0)
1033 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
1036 static void match_assign_sub(struct expression
*expr
)
1038 struct expression
*right
;
1039 struct expression
*r_left
, *r_right
;
1043 right
= strip_expr(expr
->right
);
1044 r_left
= strip_expr(right
->left
);
1045 r_right
= strip_expr(right
->right
);
1047 if (get_absolute_min(r_right
, &min
) && sval_is_negative(min
))
1050 comparison
= get_comparison(r_left
, r_right
);
1052 switch (comparison
) {
1055 if (implied_not_equal(r_right
, 0))
1056 add_comparison(expr
->left
, '>', r_left
);
1058 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
1063 static void match_assign_divide(struct expression
*expr
)
1065 struct expression
*right
;
1066 struct expression
*r_left
, *r_right
;
1069 right
= strip_expr(expr
->right
);
1070 r_left
= strip_expr(right
->left
);
1071 r_right
= strip_expr(right
->right
);
1072 if (!get_implied_min(r_right
, &min
) || min
.value
<= 1)
1075 add_comparison(expr
->left
, '<', r_left
);
1078 static void match_binop_assign(struct expression
*expr
)
1080 struct expression
*right
;
1082 right
= strip_expr(expr
->right
);
1083 if (right
->op
== '+')
1084 match_assign_add(expr
);
1085 if (right
->op
== '-')
1086 match_assign_sub(expr
);
1087 if (right
->op
== '/')
1088 match_assign_divide(expr
);
1091 static void copy_comparisons(struct expression
*left
, struct expression
*right
)
1093 struct string_list
*links
;
1094 struct smatch_state
*state
;
1095 struct compare_data
*data
;
1096 struct symbol
*left_sym
, *right_sym
;
1097 char *left_var
= NULL
;
1098 char *right_var
= NULL
;
1099 struct var_sym_list
*left_vsl
;
1101 struct var_sym_list
*vsl
;
1105 left_var
= chunk_to_var_sym(left
, &left_sym
);
1108 left_vsl
= expr_to_vsl(left
);
1109 right_var
= chunk_to_var_sym(right
, &right_sym
);
1113 state
= get_state(link_id
, right_var
, right_sym
);
1116 links
= state
->data
;
1118 FOR_EACH_PTR(links
, tmp
) {
1119 state
= get_state(compare_id
, tmp
, NULL
);
1120 if (!state
|| !state
->data
)
1123 comparison
= data
->comparison
;
1126 if (strcmp(var
, right_var
) == 0) {
1129 comparison
= flip_comparison(comparison
);
1131 add_comparison_var_sym(left_var
, left_vsl
, comparison
, var
, vsl
);
1132 } END_FOR_EACH_PTR(tmp
);
1135 free_string(right_var
);
1138 static void match_assign(struct expression
*expr
)
1140 struct expression
*right
;
1142 if (expr
->op
!= '=')
1145 if (is_struct(expr
->left
))
1148 copy_comparisons(expr
->left
, expr
->right
);
1149 add_comparison(expr
->left
, SPECIAL_EQUAL
, expr
->right
);
1151 right
= strip_expr(expr
->right
);
1152 if (right
->type
== EXPR_BINOP
)
1153 match_binop_assign(expr
);
1156 int get_comparison_strings(const char *one
, const char *two
)
1159 struct smatch_state
*state
;
1163 if (strcmp(one
, two
) == 0)
1164 return SPECIAL_EQUAL
;
1166 if (strcmp(one
, two
) > 0) {
1167 const char *tmp
= one
;
1174 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
1175 state
= get_state(compare_id
, buf
, NULL
);
1177 ret
= state_to_comparison(state
);
1180 ret
= flip_comparison(ret
);
1185 int get_comparison(struct expression
*a
, struct expression
*b
)
1191 one
= chunk_to_var(a
);
1194 two
= chunk_to_var(b
);
1198 ret
= get_comparison_strings(one
, two
);
1205 int possible_comparison(struct expression
*a
, int comparison
, struct expression
*b
)
1211 struct sm_state
*sm
;
1214 one
= chunk_to_var(a
);
1217 two
= chunk_to_var(b
);
1222 if (strcmp(one
, two
) == 0 && comparison
== SPECIAL_EQUAL
) {
1227 if (strcmp(one
, two
) > 0) {
1232 comparison
= flip_comparison(comparison
);
1235 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
1236 sm
= get_sm_state(compare_id
, buf
, NULL
);
1240 FOR_EACH_PTR(sm
->possible
, sm
) {
1241 if (!sm
->state
->data
)
1243 saved
= ((struct compare_data
*)sm
->state
->data
)->comparison
;
1244 if (saved
== comparison
)
1246 if (comparison
== SPECIAL_EQUAL
&&
1247 (saved
== SPECIAL_LTE
||
1248 saved
== SPECIAL_GTE
||
1249 saved
== SPECIAL_UNSIGNED_LTE
||
1250 saved
== SPECIAL_UNSIGNED_GTE
))
1254 } END_FOR_EACH_PTR(sm
);
1263 struct state_list
*get_all_comparisons(struct expression
*expr
)
1265 struct smatch_state
*state
;
1266 struct string_list
*links
;
1267 struct state_list
*ret
= NULL
;
1268 struct sm_state
*sm
;
1271 state
= get_state_expr(link_id
, expr
);
1274 links
= state
->data
;
1276 FOR_EACH_PTR(links
, tmp
) {
1277 sm
= get_sm_state(compare_id
, tmp
, NULL
);
1280 // FIXME have to compare name with vsl
1281 add_ptr_list(&ret
, sm
);
1282 } END_FOR_EACH_PTR(tmp
);
1287 struct state_list
*get_all_possible_equal_comparisons(struct expression
*expr
)
1289 struct smatch_state
*state
;
1290 struct string_list
*links
;
1291 struct state_list
*ret
= NULL
;
1292 struct sm_state
*sm
;
1295 state
= get_state_expr(link_id
, expr
);
1298 links
= state
->data
;
1300 FOR_EACH_PTR(links
, tmp
) {
1301 sm
= get_sm_state(compare_id
, tmp
, NULL
);
1304 if (!strchr(sm
->state
->name
, '='))
1306 if (strcmp(sm
->state
->name
, "!=") == 0)
1308 add_ptr_list(&ret
, sm
);
1309 } END_FOR_EACH_PTR(tmp
);
1314 static void update_links_from_call(struct expression
*left
,
1316 struct expression
*right
)
1318 struct string_list
*links
;
1319 struct smatch_state
*state
;
1320 struct compare_data
*data
;
1321 struct symbol
*left_sym
, *right_sym
;
1322 char *left_var
= NULL
;
1323 char *right_var
= NULL
;
1324 struct var_sym_list
*left_vsl
;
1326 struct var_sym_list
*vsl
;
1330 left_var
= chunk_to_var_sym(left
, &left_sym
);
1333 left_vsl
= expr_to_vsl(left
);
1334 right_var
= chunk_to_var_sym(right
, &right_sym
);
1338 state
= get_state(link_id
, right_var
, right_sym
);
1341 links
= state
->data
;
1343 FOR_EACH_PTR(links
, tmp
) {
1344 state
= get_state(compare_id
, tmp
, NULL
);
1345 if (!state
|| !state
->data
)
1348 comparison
= data
->comparison
;
1351 if (strcmp(var
, right_var
) == 0) {
1354 comparison
= flip_comparison(comparison
);
1356 comparison
= combine_comparisons(left_compare
, comparison
);
1359 add_comparison_var_sym(left_var
, left_vsl
, comparison
, var
, vsl
);
1360 } END_FOR_EACH_PTR(tmp
);
1363 free_string(right_var
);
1366 void __add_comparison_info(struct expression
*expr
, struct expression
*call
, const char *range
)
1368 struct expression
*arg
;
1370 const char *c
= range
;
1372 if (!str_to_comparison_arg(c
, call
, &comparison
, &arg
))
1374 update_links_from_call(expr
, comparison
, arg
);
1375 add_comparison(expr
, comparison
, arg
);
1378 static char *range_comparison_to_param_helper(struct expression
*expr
, char starts_with
, int ignore
)
1380 struct symbol
*param
;
1383 char *ret_str
= NULL
;
1387 var
= chunk_to_var(expr
);
1392 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
1398 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
1399 compare
= get_comparison_strings(var
, buf
);
1402 if (show_special(compare
)[0] != starts_with
)
1404 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_special(compare
), i
);
1405 ret_str
= alloc_sname(buf
);
1407 } END_FOR_EACH_PTR(param
);
1414 char *expr_equal_to_param(struct expression
*expr
, int ignore
)
1416 return range_comparison_to_param_helper(expr
, '=', ignore
);
1419 char *expr_lte_to_param(struct expression
*expr
, int ignore
)
1421 return range_comparison_to_param_helper(expr
, '<', ignore
);
1424 char *expr_param_comparison(struct expression
*expr
, int ignore
)
1426 struct symbol
*param
;
1429 char *ret_str
= NULL
;
1433 var
= chunk_to_var(expr
);
1438 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
1444 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
1445 compare
= get_comparison_strings(var
, buf
);
1448 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_special(compare
), i
);
1449 ret_str
= alloc_sname(buf
);
1451 } END_FOR_EACH_PTR(param
);
1458 static void free_data(struct symbol
*sym
)
1462 clear_compare_data_alloc();
1465 void register_comparison(int id
)
1468 add_hook(&match_compare
, CONDITION_HOOK
);
1469 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
1470 add_hook(&save_start_states
, AFTER_DEF_HOOK
);
1471 add_unmatched_state_hook(compare_id
, unmatched_comparison
);
1472 add_merge_hook(compare_id
, &merge_compare_states
);
1473 add_hook(&free_data
, AFTER_FUNC_HOOK
);
1476 void register_comparison_links(int id
)
1479 add_merge_hook(link_id
, &merge_links
);
1480 add_modification_hook(link_id
, &match_modify
);