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
;
37 static int inc_dec_id
;
38 static int inc_dec_link_id
;
40 /* for handling for loops */
44 ALLOCATOR(compare_data
, "compare data");
46 static struct symbol
*vsl_to_sym(struct var_sym_list
*vsl
)
52 if (ptr_list_size((struct ptr_list
*)vsl
) != 1)
54 vs
= first_ptr_list((struct ptr_list
*)vsl
);
58 struct smatch_state
*alloc_compare_state(
59 struct expression
*left
,
60 const char *left_var
, struct var_sym_list
*left_vsl
,
62 struct expression
*right
,
63 const char *right_var
, struct var_sym_list
*right_vsl
)
65 struct smatch_state
*state
;
66 struct compare_data
*data
;
68 state
= __alloc_smatch_state(0);
69 state
->name
= alloc_sname(show_special(comparison
));
70 data
= __alloc_compare_data(0);
72 data
->left_var
= alloc_sname(left_var
);
73 data
->left_vsl
= clone_var_sym_list(left_vsl
);
74 data
->comparison
= comparison
;
76 data
->right_var
= alloc_sname(right_var
);
77 data
->right_vsl
= clone_var_sym_list(right_vsl
);
82 int state_to_comparison(struct smatch_state
*state
)
84 if (!state
|| !state
->data
)
86 return ((struct compare_data
*)state
->data
)->comparison
;
90 * flip_comparison() reverses the op left and right. So "x >= y" becomes "y <= x".
92 int flip_comparison(int op
)
99 case SPECIAL_UNSIGNED_LT
:
100 return SPECIAL_UNSIGNED_GT
;
103 case SPECIAL_UNSIGNED_LTE
:
104 return SPECIAL_UNSIGNED_GTE
;
106 return SPECIAL_EQUAL
;
107 case SPECIAL_NOTEQUAL
:
108 return SPECIAL_NOTEQUAL
;
111 case SPECIAL_UNSIGNED_GTE
:
112 return SPECIAL_UNSIGNED_LTE
;
115 case SPECIAL_UNSIGNED_GT
:
116 return SPECIAL_UNSIGNED_LT
;
118 sm_msg("internal smatch bug. unhandled comparison %d", op
);
123 int negate_comparison(int op
)
130 case SPECIAL_UNSIGNED_LT
:
131 return SPECIAL_UNSIGNED_GTE
;
134 case SPECIAL_UNSIGNED_LTE
:
135 return SPECIAL_UNSIGNED_GT
;
137 return SPECIAL_NOTEQUAL
;
138 case SPECIAL_NOTEQUAL
:
139 return SPECIAL_EQUAL
;
142 case SPECIAL_UNSIGNED_GTE
:
143 return SPECIAL_UNSIGNED_LT
;
146 case SPECIAL_UNSIGNED_GT
:
147 return SPECIAL_UNSIGNED_LTE
;
149 sm_msg("internal smatch bug. unhandled comparison %d", op
);
154 static int rl_comparison(struct range_list
*left_rl
, struct range_list
*right_rl
)
156 sval_t left_min
, left_max
, right_min
, right_max
;
158 if (!left_rl
|| !right_rl
)
161 left_min
= rl_min(left_rl
);
162 left_max
= rl_max(left_rl
);
163 right_min
= rl_min(right_rl
);
164 right_max
= rl_max(right_rl
);
166 if (left_min
.value
== left_max
.value
&&
167 right_min
.value
== right_max
.value
&&
168 left_min
.value
== right_min
.value
)
169 return SPECIAL_EQUAL
;
171 if (sval_cmp(left_max
, right_min
) < 0)
173 if (sval_cmp(left_max
, right_min
) == 0)
175 if (sval_cmp(left_min
, right_max
) > 0)
177 if (sval_cmp(left_min
, right_max
) == 0)
183 static struct range_list
*get_orig_rl(struct var_sym_list
*vsl
)
186 struct smatch_state
*state
;
190 sym
= vsl_to_sym(vsl
);
191 if (!sym
|| !sym
->ident
)
193 state
= get_orig_estate(sym
->ident
->name
, sym
);
194 return estate_rl(state
);
197 static struct smatch_state
*unmatched_comparison(struct sm_state
*sm
)
199 struct compare_data
*data
= sm
->state
->data
;
200 struct range_list
*left_rl
, *right_rl
;
206 if (strstr(data
->left_var
, " orig"))
207 left_rl
= get_orig_rl(data
->left_vsl
);
208 else if (!get_implied_rl_var_sym(data
->left_var
, vsl_to_sym(data
->left_vsl
), &left_rl
))
210 if (strstr(data
->right_var
, " orig"))
211 right_rl
= get_orig_rl(data
->right_vsl
);
212 else if (!get_implied_rl_var_sym(data
->right_var
, vsl_to_sym(data
->right_vsl
), &right_rl
))
216 op
= rl_comparison(left_rl
, right_rl
);
218 return alloc_compare_state(
219 data
->left
, data
->left_var
, data
->left_vsl
,
221 data
->right
, data
->right_var
, data
->right_vsl
);
226 /* remove_unsigned_from_comparison() is obviously a hack. */
227 int remove_unsigned_from_comparison(int op
)
230 case SPECIAL_UNSIGNED_LT
:
232 case SPECIAL_UNSIGNED_LTE
:
234 case SPECIAL_UNSIGNED_GTE
:
236 case SPECIAL_UNSIGNED_GT
:
244 * This is for when you merge states "a < b" and "a == b", the result is that
245 * we can say for sure, "a <= b" after the merge.
247 int merge_comparisons(int one
, int two
)
254 one
= remove_unsigned_from_comparison(one
);
255 two
= remove_unsigned_from_comparison(two
);
305 return SPECIAL_NOTEQUAL
;
316 * This is for if you have "a < b" and "b <= c". Or in other words,
317 * "a < b <= c". You would call this like get_combined_comparison('<', '<=').
318 * The return comparison would be '<'.
320 * This function is different from merge_comparisons(), for example:
321 * merge_comparison('<', '==') returns '<='
322 * get_combined_comparison('<', '==') returns '<'
324 int combine_comparisons(int left_compare
, int right_compare
)
328 left_compare
= remove_unsigned_from_comparison(left_compare
);
329 right_compare
= remove_unsigned_from_comparison(right_compare
);
333 switch (left_compare
) {
342 return right_compare
;
351 switch (right_compare
) {
383 static int filter_comparison(int orig
, int op
)
395 case SPECIAL_NOTEQUAL
:
405 case SPECIAL_NOTEQUAL
:
414 case SPECIAL_UNSIGNED_LTE
:
415 case SPECIAL_UNSIGNED_GTE
:
416 return SPECIAL_EQUAL
;
419 case SPECIAL_NOTEQUAL
:
424 case SPECIAL_UNSIGNED_LT
:
425 case SPECIAL_UNSIGNED_LTE
:
426 return SPECIAL_UNSIGNED_LT
;
427 case SPECIAL_NOTEQUAL
:
432 case SPECIAL_UNSIGNED_GT
:
433 case SPECIAL_UNSIGNED_GTE
:
434 return SPECIAL_UNSIGNED_GT
;
440 return SPECIAL_EQUAL
;
445 case SPECIAL_NOTEQUAL
:
453 case SPECIAL_NOTEQUAL
:
457 case SPECIAL_UNSIGNED_LT
:
459 case SPECIAL_UNSIGNED_LT
:
460 case SPECIAL_UNSIGNED_LTE
:
461 case SPECIAL_NOTEQUAL
:
462 return SPECIAL_UNSIGNED_LT
;
465 case SPECIAL_UNSIGNED_LTE
:
467 case SPECIAL_UNSIGNED_LT
:
468 case SPECIAL_UNSIGNED_LTE
:
471 case SPECIAL_NOTEQUAL
:
472 return SPECIAL_UNSIGNED_LT
;
473 case SPECIAL_UNSIGNED_GTE
:
474 return SPECIAL_EQUAL
;
477 case SPECIAL_UNSIGNED_GTE
:
479 case SPECIAL_UNSIGNED_LTE
:
480 return SPECIAL_EQUAL
;
481 case SPECIAL_NOTEQUAL
:
482 return SPECIAL_UNSIGNED_GT
;
484 case SPECIAL_UNSIGNED_GTE
:
485 case SPECIAL_UNSIGNED_GT
:
489 case SPECIAL_UNSIGNED_GT
:
491 case SPECIAL_UNSIGNED_GT
:
492 case SPECIAL_UNSIGNED_GTE
:
493 case SPECIAL_NOTEQUAL
:
494 return SPECIAL_UNSIGNED_GT
;
501 struct smatch_state
*merge_compare_states(struct smatch_state
*s1
, struct smatch_state
*s2
)
503 struct compare_data
*data
= s1
->data
;
506 op
= merge_comparisons(state_to_comparison(s1
), state_to_comparison(s2
));
508 return alloc_compare_state(
509 data
->left
, data
->left_var
, data
->left_vsl
,
511 data
->right
, data
->right_var
, data
->right_vsl
);
515 static struct smatch_state
*alloc_link_state(struct string_list
*links
)
517 struct smatch_state
*state
;
518 static char buf
[256];
522 state
= __alloc_smatch_state(0);
525 FOR_EACH_PTR(links
, tmp
) {
527 snprintf(buf
, sizeof(buf
), "%s", tmp
);
529 append(buf
, ", ", sizeof(buf
));
530 append(buf
, tmp
, sizeof(buf
));
532 } END_FOR_EACH_PTR(tmp
);
534 state
->name
= alloc_sname(buf
);
539 static void save_start_states(struct statement
*stmt
)
541 struct symbol
*param
;
543 char state_name
[128];
544 struct smatch_state
*state
;
545 struct string_list
*links
;
548 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
549 struct var_sym_list
*left_vsl
= NULL
;
550 struct var_sym_list
*right_vsl
= NULL
;
554 snprintf(orig
, sizeof(orig
), "%s orig", param
->ident
->name
);
555 snprintf(state_name
, sizeof(state_name
), "%s vs %s", param
->ident
->name
, orig
);
556 add_var_sym(&left_vsl
, param
->ident
->name
, param
);
557 add_var_sym(&right_vsl
, orig
, param
);
558 state
= alloc_compare_state(
559 NULL
, param
->ident
->name
, left_vsl
,
561 NULL
, alloc_sname(orig
), right_vsl
);
562 set_state(compare_id
, state_name
, NULL
, state
);
564 link
= alloc_sname(state_name
);
566 insert_string(&links
, link
);
567 state
= alloc_link_state(links
);
568 set_state(link_id
, param
->ident
->name
, param
, state
);
569 } END_FOR_EACH_PTR(param
);
572 static struct smatch_state
*merge_links(struct smatch_state
*s1
, struct smatch_state
*s2
)
574 struct smatch_state
*ret
;
575 struct string_list
*links
;
577 links
= combine_string_lists(s1
->data
, s2
->data
);
578 ret
= alloc_link_state(links
);
582 static void save_link_var_sym(const char *var
, struct symbol
*sym
, const char *link
)
584 struct smatch_state
*old_state
, *new_state
;
585 struct string_list
*links
;
588 old_state
= get_state(link_id
, var
, sym
);
590 links
= clone_str_list(old_state
->data
);
594 new = alloc_sname(link
);
595 insert_string(&links
, new);
597 new_state
= alloc_link_state(links
);
598 set_state(link_id
, var
, sym
, new_state
);
601 static void match_inc(struct sm_state
*sm
)
603 struct string_list
*links
;
604 struct smatch_state
*state
;
609 links
= sm
->state
->data
;
611 FOR_EACH_PTR(links
, tmp
) {
612 state
= get_state(compare_id
, tmp
, NULL
);
615 if (strncmp(sm
->name
, tmp
, strlen(sm
->name
)) != 0 ||
616 tmp
[strlen(sm
->name
)] != ' ')
619 op
= state_to_comparison(state
);
621 switch (flip
? flip_comparison(op
) : op
) {
624 case SPECIAL_UNSIGNED_GTE
:
626 case SPECIAL_UNSIGNED_GT
: {
627 struct compare_data
*data
= state
->data
;
628 struct smatch_state
*new;
630 new = alloc_compare_state(
631 data
->left
, data
->left_var
, data
->left_vsl
,
633 data
->right
, data
->right_var
, data
->right_vsl
);
634 set_state(compare_id
, tmp
, NULL
, new);
638 set_state(compare_id
, tmp
, NULL
, &undefined
);
640 } END_FOR_EACH_PTR(tmp
);
643 static void match_dec(struct sm_state
*sm
)
645 struct string_list
*links
;
646 struct smatch_state
*state
;
649 links
= sm
->state
->data
;
651 FOR_EACH_PTR(links
, tmp
) {
652 state
= get_state(compare_id
, tmp
, NULL
);
654 switch (state_to_comparison(state
)) {
657 case SPECIAL_UNSIGNED_LTE
:
659 case SPECIAL_UNSIGNED_LT
: {
660 struct compare_data
*data
= state
->data
;
661 struct smatch_state
*new;
663 new = alloc_compare_state(
664 data
->left
, data
->left_var
, data
->left_vsl
,
666 data
->right
, data
->right_var
, data
->right_vsl
);
667 set_state(compare_id
, tmp
, NULL
, new);
671 set_state(compare_id
, tmp
, NULL
, &undefined
);
673 } END_FOR_EACH_PTR(tmp
);
676 static int match_inc_dec(struct sm_state
*sm
, struct expression
*mod_expr
)
680 if (mod_expr
->type
!= EXPR_PREOP
&& mod_expr
->type
!= EXPR_POSTOP
)
683 if (mod_expr
->op
== SPECIAL_INCREMENT
) {
687 if (mod_expr
->op
== SPECIAL_DECREMENT
) {
694 static void match_modify(struct sm_state
*sm
, struct expression
*mod_expr
)
696 struct string_list
*links
;
700 * if (foo > bar) then ++foo is also > bar.
702 if (match_inc_dec(sm
, mod_expr
))
705 links
= sm
->state
->data
;
707 FOR_EACH_PTR(links
, tmp
) {
708 set_state(compare_id
, tmp
, NULL
, &undefined
);
709 } END_FOR_EACH_PTR(tmp
);
710 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
713 static char *chunk_to_var_sym(struct expression
*expr
, struct symbol
**sym
)
715 expr
= strip_expr(expr
);
721 if (expr
->type
== EXPR_PREOP
&&
722 (expr
->op
== SPECIAL_INCREMENT
||
723 expr
->op
== SPECIAL_DECREMENT
))
724 expr
= strip_expr(expr
->unop
);
726 if (expr
->type
== EXPR_CALL
) {
729 snprintf(buf
, sizeof(buf
), "return %p", expr
);
730 return alloc_string(buf
);
733 return expr_to_chunk_sym_vsl(expr
, sym
, NULL
);
736 static char *chunk_to_var(struct expression
*expr
)
738 return chunk_to_var_sym(expr
, NULL
);
741 static struct smatch_state
*get_state_chunk(int owner
, struct expression
*expr
)
745 struct smatch_state
*ret
;
747 name
= chunk_to_var_sym(expr
, &sym
);
751 ret
= get_state(owner
, name
, sym
);
756 static void save_link(struct expression
*expr
, char *link
)
761 expr
= strip_expr(expr
);
762 if (expr
->type
== EXPR_BINOP
) {
765 chunk
= chunk_to_var(expr
);
769 save_link(expr
->left
, link
);
770 save_link(expr
->right
, link
);
771 save_link_var_sym(chunk
, NULL
, link
);
775 var
= chunk_to_var_sym(expr
, &sym
);
779 save_link_var_sym(var
, sym
, link
);
783 static int get_orig_comparison(struct stree
*pre_stree
, const char *left
, const char *right
)
785 struct smatch_state
*state
;
786 struct compare_data
*data
;
788 char state_name
[256];
790 if (strcmp(left
, right
) > 0) {
791 const char *tmp
= right
;
798 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
799 state
= get_state_stree(pre_stree
, compare_id
, state_name
, NULL
);
800 if (!state
|| !state
->data
)
804 return flip_comparison(data
->comparison
);
805 return data
->comparison
;
809 static int have_common_var_sym(struct var_sym_list
*left_vsl
, struct var_sym_list
*right_vsl
)
813 FOR_EACH_PTR(left_vsl
, tmp
) {
814 if (in_var_sym_list(right_vsl
, tmp
->var
, tmp
->sym
))
816 } END_FOR_EACH_PTR(tmp
);
822 * The idea here is that we take a comparison "a < b" and then we look at all
823 * the things which "b" is compared against "b < c" and we say that that implies
824 * a relationship "a < c".
826 * The names here about because the comparisons are organized like this
830 static void update_tf_links(struct stree
*pre_stree
,
831 struct expression
*left_expr
,
832 const char *left_var
, struct var_sym_list
*left_vsl
,
833 int left_comparison
, int left_false_comparison
,
834 const char *mid_var
, struct var_sym_list
*mid_vsl
,
835 struct string_list
*links
)
837 struct smatch_state
*state
;
838 struct smatch_state
*true_state
, *false_state
;
839 struct compare_data
*data
;
840 struct expression
*right_expr
;
841 const char *right_var
;
842 struct var_sym_list
*right_vsl
;
844 int right_comparison
;
846 int false_comparison
;
848 char state_name
[256];
851 FOR_EACH_PTR(links
, tmp
) {
852 state
= get_state_stree(pre_stree
, compare_id
, tmp
, NULL
);
853 if (!state
|| !state
->data
)
856 right_comparison
= data
->comparison
;
857 right_expr
= data
->right
;
858 right_var
= data
->right_var
;
859 right_vsl
= data
->right_vsl
;
860 if (strcmp(mid_var
, right_var
) == 0) {
861 right_expr
= data
->left
;
862 right_var
= data
->left_var
;
863 right_vsl
= data
->left_vsl
;
864 right_comparison
= flip_comparison(right_comparison
);
866 if (have_common_var_sym(left_vsl
, right_vsl
))
869 orig_comparison
= get_orig_comparison(pre_stree
, left_var
, right_var
);
871 true_comparison
= combine_comparisons(left_comparison
, right_comparison
);
872 false_comparison
= combine_comparisons(left_false_comparison
, right_comparison
);
874 true_comparison
= filter_comparison(orig_comparison
, true_comparison
);
875 false_comparison
= filter_comparison(orig_comparison
, false_comparison
);
877 if (strcmp(left_var
, right_var
) > 0) {
878 struct expression
*tmp_expr
= left_expr
;
879 const char *tmp_var
= left_var
;
880 struct var_sym_list
*tmp_vsl
= left_vsl
;
882 left_expr
= right_expr
;
883 left_var
= right_var
;
884 left_vsl
= right_vsl
;
885 right_expr
= tmp_expr
;
888 true_comparison
= flip_comparison(true_comparison
);
889 false_comparison
= flip_comparison(false_comparison
);
892 if (!true_comparison
&& !false_comparison
)
896 true_state
= alloc_compare_state(
897 left_expr
, left_var
, left_vsl
,
899 right_expr
, right_var
, right_vsl
);
902 if (false_comparison
)
903 false_state
= alloc_compare_state(
904 left_expr
, left_var
, left_vsl
,
906 right_expr
, right_var
, right_vsl
);
910 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_var
, right_var
);
911 set_true_false_states(compare_id
, state_name
, NULL
, true_state
, false_state
);
912 FOR_EACH_PTR(left_vsl
, vs
) {
913 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
914 } END_FOR_EACH_PTR(vs
);
915 FOR_EACH_PTR(right_vsl
, vs
) {
916 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
917 } END_FOR_EACH_PTR(vs
);
918 if (!vsl_to_sym(left_vsl
))
919 save_link_var_sym(left_var
, NULL
, state_name
);
920 if (!vsl_to_sym(right_vsl
))
921 save_link_var_sym(right_var
, NULL
, state_name
);
922 } END_FOR_EACH_PTR(tmp
);
925 static void update_tf_data(struct stree
*pre_stree
,
926 struct expression
*left_expr
,
927 const char *left_name
, struct var_sym_list
*left_vsl
,
928 struct expression
*right_expr
,
929 const char *right_name
, struct var_sym_list
*right_vsl
,
930 int true_comparison
, int false_comparison
)
932 struct smatch_state
*state
;
934 state
= get_state_stree(pre_stree
, link_id
, right_name
, vsl_to_sym(right_vsl
));
936 update_tf_links(pre_stree
, left_expr
, left_name
, left_vsl
, true_comparison
, false_comparison
, right_name
, right_vsl
, state
->data
);
938 state
= get_state_stree(pre_stree
, link_id
, left_name
, vsl_to_sym(left_vsl
));
940 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
);
943 static void iter_modify(struct sm_state
*sm
, struct expression
*mod_expr
)
945 if (sm
->state
!= &start
||
947 (mod_expr
->type
!= EXPR_PREOP
&& mod_expr
->type
!= EXPR_POSTOP
) ||
948 mod_expr
->op
!= SPECIAL_INCREMENT
)
949 set_state(inc_dec_id
, sm
->name
, sm
->sym
, &undefined
);
951 set_state(inc_dec_id
, sm
->name
, sm
->sym
, &incremented
);
954 static void handle_for_loops(struct expression
*expr
, char *state_name
, struct smatch_state
*false_state
)
957 char *iter_name
, *cap_name
;
958 struct symbol
*iter_sym
, *cap_sym
;
959 struct compare_data
*data
;
961 if (expr
->op
!= '<' && expr
->op
!= SPECIAL_UNSIGNED_LT
)
964 if (!__cur_stmt
|| !__prev_stmt
)
966 if (__cur_stmt
->type
!= STMT_ITERATOR
)
968 if (__cur_stmt
->iterator_pre_condition
!= expr
)
971 /* literals are handled in smatch_extra.c */
972 if (get_value(expr
->right
, &sval
))
975 /* First time checking the condition */
976 if (__prev_stmt
== __cur_stmt
->iterator_pre_statement
) {
977 if (!get_implied_value(expr
->left
, &sval
) ||
981 iter_name
= expr_to_var_sym(expr
->left
, &iter_sym
);
982 cap_name
= expr_to_var_sym(expr
->right
, &cap_sym
);
983 if (!iter_name
|| !cap_name
|| !iter_sym
|| !cap_sym
) {
984 free_string(iter_name
);
985 free_string(cap_name
);
989 set_state(inc_dec_id
, iter_name
, iter_sym
, &start
);
990 store_link(inc_dec_link_id
, cap_name
, cap_sym
, iter_name
, iter_sym
);
992 free_string(iter_name
);
993 free_string(cap_name
);
997 /* Second time checking the condtion */
998 if (__prev_stmt
!= __cur_stmt
->iterator_post_statement
)
1001 if (get_state_chunk(inc_dec_id
, expr
->left
) != &incremented
)
1004 data
= false_state
->data
;
1005 false_state
= alloc_compare_state(
1006 data
->left
, data
->left_var
, data
->left_vsl
,
1008 data
->right
, data
->right_var
, data
->right_vsl
);
1010 set_true_false_states(compare_id
, state_name
, NULL
, NULL
, false_state
);
1013 static void handle_comparison(struct expression
*left_expr
, int op
, struct expression
*right_expr
, char **_state_name
, struct smatch_state
**_false_state
)
1017 struct symbol
*left_sym
, *right_sym
;
1018 struct var_sym_list
*left_vsl
, *right_vsl
;
1020 int orig_comparison
;
1021 struct smatch_state
*true_state
, *false_state
;
1022 static char state_name
[256];
1023 struct stree
*pre_stree
;
1026 false_op
= negate_comparison(op
);
1028 if (op
== SPECIAL_UNSIGNED_LT
&&
1029 get_implied_value(left_expr
, &sval
) &&
1031 false_op
= SPECIAL_EQUAL
;
1033 if (op
== SPECIAL_UNSIGNED_GT
&&
1034 get_implied_value(right_expr
, &sval
) &&
1036 false_op
= SPECIAL_EQUAL
;
1038 left
= chunk_to_var_sym(left_expr
, &left_sym
);
1041 left_vsl
= expr_to_vsl(left_expr
);
1042 right
= chunk_to_var_sym(right_expr
, &right_sym
);
1045 right_vsl
= expr_to_vsl(right_expr
);
1047 if (strcmp(left
, right
) > 0) {
1048 struct symbol
*tmp_sym
= left_sym
;
1049 char *tmp_name
= left
;
1050 struct var_sym_list
*tmp_vsl
= left_vsl
;
1051 struct expression
*tmp_expr
= left_expr
;
1054 left_sym
= right_sym
;
1055 left_vsl
= right_vsl
;
1056 left_expr
= right_expr
;
1058 right_sym
= tmp_sym
;
1059 right_vsl
= tmp_vsl
;
1060 right_expr
= tmp_expr
;
1061 op
= flip_comparison(op
);
1062 false_op
= flip_comparison(false_op
);
1065 orig_comparison
= get_comparison_strings(left
, right
);
1066 op
= filter_comparison(orig_comparison
, op
);
1067 false_op
= filter_comparison(orig_comparison
, false_op
);
1069 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
1070 true_state
= alloc_compare_state(
1071 left_expr
, left
, left_vsl
,
1073 right_expr
, right
, right_vsl
);
1074 false_state
= alloc_compare_state(
1075 left_expr
, left
, left_vsl
,
1077 right_expr
, right
, right_vsl
);
1079 pre_stree
= clone_stree(__get_cur_stree());
1080 update_tf_data(pre_stree
, left_expr
, left
, left_vsl
, right_expr
, right
, right_vsl
, op
, false_op
);
1081 free_stree(&pre_stree
);
1083 set_true_false_states(compare_id
, state_name
, NULL
, true_state
, false_state
);
1084 __compare_param_limit_hook(left_expr
, right_expr
, state_name
, true_state
, false_state
);
1085 save_link(left_expr
, state_name
);
1086 save_link(right_expr
, state_name
);
1089 *_false_state
= false_state
;
1091 *_state_name
= state_name
;
1098 void __comparison_match_condition(struct expression
*expr
)
1100 struct expression
*left
, *right
, *new_left
, *new_right
;
1101 struct smatch_state
*false_state
= NULL
;
1102 char *state_name
= NULL
;
1104 if (expr
->type
!= EXPR_COMPARE
)
1107 handle_comparison(expr
->left
, expr
->op
, expr
->right
, &state_name
, &false_state
);
1108 if (false_state
&& state_name
)
1109 handle_for_loops(expr
, state_name
, false_state
);
1112 left
= strip_parens(expr
->left
);
1113 right
= strip_parens(expr
->right
);
1115 if (left
->type
== EXPR_BINOP
&& left
->op
== '+') {
1116 new_left
= left
->left
;
1117 new_right
= binop_expression(right
, '-', left
->right
);
1118 handle_comparison(new_left
, expr
->op
, new_right
, NULL
, NULL
);
1120 new_left
= left
->right
;
1121 new_right
= binop_expression(right
, '-', left
->left
);
1122 handle_comparison(new_left
, expr
->op
, new_right
, NULL
, NULL
);
1126 static void add_comparison_var_sym(
1127 struct expression
*left_expr
,
1128 const char *left_name
, struct var_sym_list
*left_vsl
,
1130 struct expression
*right_expr
,
1131 const char *right_name
, struct var_sym_list
*right_vsl
)
1133 struct smatch_state
*state
;
1135 char state_name
[256];
1137 if (strcmp(left_name
, right_name
) > 0) {
1138 struct expression
*tmp_expr
= left_expr
;
1139 const char *tmp_name
= left_name
;
1140 struct var_sym_list
*tmp_vsl
= left_vsl
;
1142 left_expr
= right_expr
;
1143 left_name
= right_name
;
1144 left_vsl
= right_vsl
;
1145 right_expr
= tmp_expr
;
1146 right_name
= tmp_name
;
1147 right_vsl
= tmp_vsl
;
1148 comparison
= flip_comparison(comparison
);
1150 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_name
, right_name
);
1151 state
= alloc_compare_state(
1152 left_expr
, left_name
, left_vsl
,
1154 right_expr
, right_name
, right_vsl
);
1156 set_state(compare_id
, state_name
, NULL
, state
);
1158 FOR_EACH_PTR(left_vsl
, vs
) {
1159 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
1160 } END_FOR_EACH_PTR(vs
);
1161 FOR_EACH_PTR(right_vsl
, vs
) {
1162 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
1163 } END_FOR_EACH_PTR(vs
);
1166 static void add_comparison(struct expression
*left
, int comparison
, struct expression
*right
)
1168 char *left_name
= NULL
;
1169 char *right_name
= NULL
;
1170 struct symbol
*left_sym
, *right_sym
;
1171 struct var_sym_list
*left_vsl
, *right_vsl
;
1172 struct smatch_state
*state
;
1173 char state_name
[256];
1175 left_name
= chunk_to_var_sym(left
, &left_sym
);
1178 left_vsl
= expr_to_vsl(left
);
1179 right_name
= chunk_to_var_sym(right
, &right_sym
);
1182 right_vsl
= expr_to_vsl(right
);
1184 if (strcmp(left_name
, right_name
) > 0) {
1185 struct expression
*tmp_expr
= left
;
1186 struct symbol
*tmp_sym
= left_sym
;
1187 char *tmp_name
= left_name
;
1188 struct var_sym_list
*tmp_vsl
= left_vsl
;
1191 left_name
= right_name
;
1192 left_sym
= right_sym
;
1193 left_vsl
= right_vsl
;
1195 right_name
= tmp_name
;
1196 right_sym
= tmp_sym
;
1197 right_vsl
= tmp_vsl
;
1198 comparison
= flip_comparison(comparison
);
1200 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_name
, right_name
);
1201 state
= alloc_compare_state(
1202 left
, left_name
, left_vsl
,
1204 right
, right_name
, right_vsl
);
1206 set_state(compare_id
, state_name
, NULL
, state
);
1207 save_link(left
, state_name
);
1208 save_link(right
, state_name
);
1211 free_string(left_name
);
1212 free_string(right_name
);
1215 static void match_assign_add(struct expression
*expr
)
1217 struct expression
*right
;
1218 struct expression
*r_left
, *r_right
;
1219 sval_t left_tmp
, right_tmp
;
1221 right
= strip_expr(expr
->right
);
1222 r_left
= strip_expr(right
->left
);
1223 r_right
= strip_expr(right
->right
);
1225 get_absolute_min(r_left
, &left_tmp
);
1226 get_absolute_min(r_right
, &right_tmp
);
1228 if (left_tmp
.value
> 0)
1229 add_comparison(expr
->left
, '>', r_right
);
1230 else if (left_tmp
.value
== 0)
1231 add_comparison(expr
->left
, SPECIAL_GTE
, r_right
);
1233 if (right_tmp
.value
> 0)
1234 add_comparison(expr
->left
, '>', r_left
);
1235 else if (right_tmp
.value
== 0)
1236 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
1239 static void match_assign_sub(struct expression
*expr
)
1241 struct expression
*right
;
1242 struct expression
*r_left
, *r_right
;
1246 right
= strip_expr(expr
->right
);
1247 r_left
= strip_expr(right
->left
);
1248 r_right
= strip_expr(right
->right
);
1250 if (get_absolute_min(r_right
, &min
) && sval_is_negative(min
))
1253 comparison
= get_comparison(r_left
, r_right
);
1255 switch (comparison
) {
1258 if (implied_not_equal(r_right
, 0))
1259 add_comparison(expr
->left
, '>', r_left
);
1261 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
1266 static void match_assign_divide(struct expression
*expr
)
1268 struct expression
*right
;
1269 struct expression
*r_left
, *r_right
;
1272 right
= strip_expr(expr
->right
);
1273 r_left
= strip_expr(right
->left
);
1274 r_right
= strip_expr(right
->right
);
1275 if (!get_implied_min(r_right
, &min
) || min
.value
<= 1)
1278 add_comparison(expr
->left
, '<', r_left
);
1281 static void match_binop_assign(struct expression
*expr
)
1283 struct expression
*right
;
1285 right
= strip_expr(expr
->right
);
1286 if (right
->op
== '+')
1287 match_assign_add(expr
);
1288 if (right
->op
== '-')
1289 match_assign_sub(expr
);
1290 if (right
->op
== '/')
1291 match_assign_divide(expr
);
1294 static void copy_comparisons(struct expression
*left
, struct expression
*right
)
1296 struct string_list
*links
;
1297 struct smatch_state
*state
;
1298 struct compare_data
*data
;
1299 struct symbol
*left_sym
, *right_sym
;
1300 char *left_var
= NULL
;
1301 char *right_var
= NULL
;
1302 struct var_sym_list
*left_vsl
;
1303 struct expression
*expr
;
1305 struct var_sym_list
*vsl
;
1309 left_var
= chunk_to_var_sym(left
, &left_sym
);
1312 left_vsl
= expr_to_vsl(left
);
1313 right_var
= chunk_to_var_sym(right
, &right_sym
);
1317 state
= get_state(link_id
, right_var
, right_sym
);
1320 links
= state
->data
;
1322 FOR_EACH_PTR(links
, tmp
) {
1323 state
= get_state(compare_id
, tmp
, NULL
);
1324 if (!state
|| !state
->data
)
1327 comparison
= data
->comparison
;
1329 var
= data
->right_var
;
1330 vsl
= data
->right_vsl
;
1331 if (strcmp(var
, right_var
) == 0) {
1333 var
= data
->left_var
;
1334 vsl
= data
->left_vsl
;
1335 comparison
= flip_comparison(comparison
);
1337 add_comparison_var_sym(left
, left_var
, left_vsl
, comparison
, expr
, var
, vsl
);
1338 } END_FOR_EACH_PTR(tmp
);
1341 free_string(right_var
);
1344 static void match_assign(struct expression
*expr
)
1346 struct expression
*right
;
1348 if (expr
->op
!= '=')
1350 if (__in_fake_assign
|| outside_of_function())
1353 if (is_struct(expr
->left
))
1356 copy_comparisons(expr
->left
, expr
->right
);
1357 add_comparison(expr
->left
, SPECIAL_EQUAL
, expr
->right
);
1359 right
= strip_expr(expr
->right
);
1360 if (right
->type
== EXPR_BINOP
)
1361 match_binop_assign(expr
);
1364 int get_comparison_strings(const char *one
, const char *two
)
1367 struct smatch_state
*state
;
1371 if (strcmp(one
, two
) == 0)
1372 return SPECIAL_EQUAL
;
1374 if (strcmp(one
, two
) > 0) {
1375 const char *tmp
= one
;
1382 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
1383 state
= get_state(compare_id
, buf
, NULL
);
1385 ret
= state_to_comparison(state
);
1388 ret
= flip_comparison(ret
);
1393 int get_comparison(struct expression
*a
, struct expression
*b
)
1399 one
= chunk_to_var(a
);
1402 two
= chunk_to_var(b
);
1406 ret
= get_comparison_strings(one
, two
);
1413 int possible_comparison(struct expression
*a
, int comparison
, struct expression
*b
)
1419 struct sm_state
*sm
;
1422 one
= chunk_to_var(a
);
1425 two
= chunk_to_var(b
);
1430 if (strcmp(one
, two
) == 0 && comparison
== SPECIAL_EQUAL
) {
1435 if (strcmp(one
, two
) > 0) {
1440 comparison
= flip_comparison(comparison
);
1443 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
1444 sm
= get_sm_state(compare_id
, buf
, NULL
);
1448 FOR_EACH_PTR(sm
->possible
, sm
) {
1449 if (!sm
->state
->data
)
1451 saved
= ((struct compare_data
*)sm
->state
->data
)->comparison
;
1452 if (saved
== comparison
)
1454 if (comparison
== SPECIAL_EQUAL
&&
1455 (saved
== SPECIAL_LTE
||
1456 saved
== SPECIAL_GTE
||
1457 saved
== SPECIAL_UNSIGNED_LTE
||
1458 saved
== SPECIAL_UNSIGNED_GTE
))
1462 } END_FOR_EACH_PTR(sm
);
1471 struct state_list
*get_all_comparisons(struct expression
*expr
)
1473 struct smatch_state
*state
;
1474 struct string_list
*links
;
1475 struct state_list
*ret
= NULL
;
1476 struct sm_state
*sm
;
1479 state
= get_state_chunk(link_id
, expr
);
1482 links
= state
->data
;
1484 FOR_EACH_PTR(links
, tmp
) {
1485 sm
= get_sm_state(compare_id
, tmp
, NULL
);
1488 // FIXME have to compare name with vsl
1489 add_ptr_list(&ret
, sm
);
1490 } END_FOR_EACH_PTR(tmp
);
1495 struct state_list
*get_all_possible_equal_comparisons(struct expression
*expr
)
1497 struct smatch_state
*state
;
1498 struct string_list
*links
;
1499 struct state_list
*ret
= NULL
;
1500 struct sm_state
*sm
;
1503 state
= get_state_chunk(link_id
, expr
);
1506 links
= state
->data
;
1508 FOR_EACH_PTR(links
, tmp
) {
1509 sm
= get_sm_state(compare_id
, tmp
, NULL
);
1512 if (!strchr(sm
->state
->name
, '='))
1514 if (strcmp(sm
->state
->name
, "!=") == 0)
1516 add_ptr_list(&ret
, sm
);
1517 } END_FOR_EACH_PTR(tmp
);
1523 static void update_links_from_call(struct expression
*left
,
1525 struct expression
*right
)
1527 struct string_list
*links
;
1528 struct smatch_state
*state
;
1529 struct compare_data
*data
;
1530 struct symbol
*left_sym
, *right_sym
;
1531 char *left_var
= NULL
;
1532 char *right_var
= NULL
;
1533 struct var_sym_list
*left_vsl
;
1534 struct expression
*expr
;
1536 struct var_sym_list
*vsl
;
1540 left_var
= chunk_to_var_sym(left
, &left_sym
);
1543 left_vsl
= expr_to_vsl(left
);
1544 right_var
= chunk_to_var_sym(right
, &right_sym
);
1548 state
= get_state(link_id
, right_var
, right_sym
);
1551 links
= state
->data
;
1553 FOR_EACH_PTR(links
, tmp
) {
1554 state
= get_state(compare_id
, tmp
, NULL
);
1555 if (!state
|| !state
->data
)
1558 comparison
= data
->comparison
;
1560 var
= data
->right_var
;
1561 vsl
= data
->right_vsl
;
1562 if (strcmp(var
, right_var
) == 0) {
1564 var
= data
->left_var
;
1565 vsl
= data
->left_vsl
;
1566 comparison
= flip_comparison(comparison
);
1568 comparison
= combine_comparisons(left_compare
, comparison
);
1571 add_comparison_var_sym(left
, left_var
, left_vsl
, comparison
, expr
, var
, vsl
);
1572 } END_FOR_EACH_PTR(tmp
);
1575 free_string(right_var
);
1578 void __add_return_comparison(struct expression
*call
, const char *range
)
1580 struct expression
*arg
;
1584 if (!str_to_comparison_arg(range
, call
, &comparison
, &arg
))
1586 snprintf(buf
, sizeof(buf
), "%s", show_special(comparison
));
1587 update_links_from_call(call
, comparison
, arg
);
1588 add_comparison(call
, comparison
, arg
);
1591 void __add_comparison_info(struct expression
*expr
, struct expression
*call
, const char *range
)
1593 copy_comparisons(expr
, call
);
1596 static char *range_comparison_to_param_helper(struct expression
*expr
, char starts_with
, int ignore
)
1598 struct symbol
*param
;
1601 char *ret_str
= NULL
;
1605 var
= chunk_to_var(expr
);
1610 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
1616 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
1617 compare
= get_comparison_strings(var
, buf
);
1620 if (show_special(compare
)[0] != starts_with
)
1622 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_special(compare
), i
);
1623 ret_str
= alloc_sname(buf
);
1625 } END_FOR_EACH_PTR(param
);
1632 char *name_sym_to_param_comparison(const char *name
, struct symbol
*sym
)
1634 struct symbol
*param
;
1640 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
1644 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
1645 compare
= get_comparison_strings(name
, buf
);
1648 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_special(compare
), i
);
1649 return alloc_sname(buf
);
1650 } END_FOR_EACH_PTR(param
);
1655 char *expr_equal_to_param(struct expression
*expr
, int ignore
)
1657 return range_comparison_to_param_helper(expr
, '=', ignore
);
1660 char *expr_lte_to_param(struct expression
*expr
, int ignore
)
1662 return range_comparison_to_param_helper(expr
, '<', ignore
);
1665 char *expr_param_comparison(struct expression
*expr
, int ignore
)
1667 struct symbol
*param
;
1670 char *ret_str
= NULL
;
1674 var
= chunk_to_var(expr
);
1679 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
1685 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
1686 compare
= get_comparison_strings(var
, buf
);
1689 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_special(compare
), i
);
1690 ret_str
= alloc_sname(buf
);
1692 } END_FOR_EACH_PTR(param
);
1699 char *get_printed_param_name(struct expression
*call
, const char *param_name
, struct symbol
*param_sym
)
1701 struct expression
*arg
;
1704 static char buf
[256];
1709 FOR_EACH_PTR(call
->args
, arg
) {
1712 name
= expr_to_var_sym(arg
, &sym
);
1715 if (sym
!= param_sym
)
1719 if (strncmp(name
, param_name
, len
) != 0)
1721 if (param_name
[len
] == '\0') {
1722 snprintf(buf
, sizeof(buf
), "$%d", i
);
1725 if (param_name
[len
] != '-')
1727 snprintf(buf
, sizeof(buf
), "$%d%s", i
, param_name
+ len
);
1729 } END_FOR_EACH_PTR(arg
);
1734 static void match_call_info(struct expression
*expr
)
1736 struct expression
*arg
;
1737 struct smatch_state
*state
;
1738 struct sm_state
*sm
;
1739 struct compare_data
*data
;
1741 struct string_list
*links
;
1743 const char *right_name
;
1749 FOR_EACH_PTR(expr
->args
, arg
) {
1752 state
= get_state_chunk(link_id
, arg
);
1756 links
= state
->data
;
1757 FOR_EACH_PTR(links
, link
) {
1758 struct var_sym_list
*right_vsl
;
1759 struct var_sym
*right_vs
;
1762 if (strstr(link
, " orig"))
1764 sm
= get_sm_state(compare_id
, link
, NULL
);
1767 data
= sm
->state
->data
;
1768 if (!data
|| !data
->comparison
)
1770 arg_name
= expr_to_var(arg
);
1775 if (strcmp(data
->left_var
, arg_name
) == 0) {
1776 comparison
= data
->comparison
;
1777 right_name
= data
->right_var
;
1778 right_vsl
= data
->right_vsl
;
1779 } else if (strcmp(data
->right_var
, arg_name
) == 0) {
1780 comparison
= flip_comparison(data
->comparison
);
1781 right_name
= data
->left_var
;
1782 right_vsl
= data
->left_vsl
;
1784 if (!right_vsl
|| ptr_list_size((struct ptr_list
*)right_vsl
) != 1)
1787 right_vs
= first_ptr_list((struct ptr_list
*)right_vsl
);
1788 if (strcmp(right_vs
->var
, right_name
) != 0)
1790 right_name
= get_printed_param_name(expr
, right_vs
->var
, right_vs
->sym
);
1793 snprintf(info_buf
, sizeof(info_buf
), "%s %s", show_special(comparison
), right_name
);
1794 sql_insert_caller_info(expr
, PARAM_COMPARE
, i
, "$", info_buf
);
1797 free_string(arg_name
);
1798 } END_FOR_EACH_PTR(link
);
1799 } END_FOR_EACH_PTR(arg
);
1802 static void struct_member_callback(struct expression
*call
, int param
, char *printed_name
, struct sm_state
*link_sm
)
1804 struct sm_state
*compare_sm
;
1805 struct string_list
*links
;
1807 struct compare_data
*data
;
1808 struct var_sym
*left
, *right
;
1809 static char info_buf
[256];
1810 const char *right_name
;
1812 if (strstr(printed_name
, " orig"))
1815 links
= link_sm
->state
->data
;
1816 FOR_EACH_PTR(links
, link
) {
1817 compare_sm
= get_sm_state(compare_id
, link
, NULL
);
1820 data
= compare_sm
->state
->data
;
1821 if (!data
|| !data
->comparison
)
1824 if (ptr_list_size((struct ptr_list
*)data
->left_vsl
) != 1 ||
1825 ptr_list_size((struct ptr_list
*)data
->right_vsl
) != 1)
1827 left
= first_ptr_list((struct ptr_list
*)data
->left_vsl
);
1828 right
= first_ptr_list((struct ptr_list
*)data
->right_vsl
);
1829 if (left
->sym
== right
->sym
&&
1830 strcmp(left
->var
, right
->var
) == 0)
1833 * Both parameters link to this comparison so only
1834 * record the first one.
1836 if (left
->sym
!= link_sm
->sym
||
1837 strcmp(left
->var
, link_sm
->name
) != 0)
1840 right_name
= get_printed_param_name(call
, right
->var
, right
->sym
);
1843 snprintf(info_buf
, sizeof(info_buf
), "%s %s", show_special(data
->comparison
), right_name
);
1844 sql_insert_caller_info(call
, PARAM_COMPARE
, param
, printed_name
, info_buf
);
1845 } END_FOR_EACH_PTR(link
);
1848 static void print_return_value_comparison(int return_id
, char *return_ranges
, struct expression
*expr
)
1851 const char *tmp_name
;
1857 * TODO: This only prints == comparisons. That's probably the most
1858 * useful comparison because == max has lots of implications. But it
1859 * would be good to capture the rest as well.
1861 * This information is already in the DB but it's in the parameter math
1862 * bits and it's awkward to use it. This is is the simpler, possibly
1863 * cleaner way, but not necessarily the best, I don't know.
1868 name
= expr_to_var_sym(expr
, &sym
);
1872 param
= get_param_num_from_sym(sym
);
1875 if (param_was_set_var_sym(name
, sym
))
1878 tmp_name
= get_param_name_var_sym(name
, sym
);
1882 snprintf(info_buf
, sizeof(info_buf
), "== $%d%s", param
, tmp_name
+ 1);
1883 sql_insert_return_states(return_id
, return_ranges
,
1884 PARAM_COMPARE
, -1, "$", info_buf
);
1889 static void print_return_comparison(int return_id
, char *return_ranges
, struct expression
*expr
)
1891 struct sm_state
*tmp
;
1892 struct string_list
*links
;
1894 struct sm_state
*sm
;
1895 struct compare_data
*data
;
1896 struct var_sym
*left
, *right
;
1897 int left_param
, right_param
;
1899 char right_buf
[256];
1901 const char *tmp_name
;
1903 print_return_value_comparison(return_id
, return_ranges
, expr
);
1905 FOR_EACH_MY_SM(link_id
, __get_cur_stree(), tmp
) {
1906 if (get_param_num_from_sym(tmp
->sym
) < 0)
1908 links
= tmp
->state
->data
;
1909 FOR_EACH_PTR(links
, link
) {
1910 sm
= get_sm_state(compare_id
, link
, NULL
);
1913 data
= sm
->state
->data
;
1914 if (!data
|| !data
->comparison
)
1916 if (ptr_list_size((struct ptr_list
*)data
->left_vsl
) != 1 ||
1917 ptr_list_size((struct ptr_list
*)data
->right_vsl
) != 1)
1919 left
= first_ptr_list((struct ptr_list
*)data
->left_vsl
);
1920 right
= first_ptr_list((struct ptr_list
*)data
->right_vsl
);
1921 if (left
->sym
== right
->sym
&&
1922 strcmp(left
->var
, right
->var
) == 0)
1925 * Both parameters link to this comparison so only
1926 * record the first one.
1928 if (left
->sym
!= tmp
->sym
||
1929 strcmp(left
->var
, tmp
->name
) != 0)
1932 if (strstr(right
->var
, " orig"))
1935 left_param
= get_param_num_from_sym(left
->sym
);
1936 right_param
= get_param_num_from_sym(right
->sym
);
1937 if (left_param
< 0 || right_param
< 0)
1940 tmp_name
= get_param_name_var_sym(left
->var
, left
->sym
);
1943 snprintf(left_buf
, sizeof(left_buf
), "%s", tmp_name
);
1945 tmp_name
= get_param_name_var_sym(right
->var
, right
->sym
);
1946 if (!tmp_name
|| tmp_name
[0] != '$')
1948 snprintf(right_buf
, sizeof(right_buf
), "$%d%s", right_param
, tmp_name
+ 1);
1951 * FIXME: this should reject $ type variables (as
1952 * opposed to $->foo type). Those should come from
1953 * smatch_param_compare_limit.c.
1956 snprintf(info_buf
, sizeof(info_buf
), "%s %s", show_special(data
->comparison
), right_buf
);
1957 sql_insert_return_states(return_id
, return_ranges
,
1958 PARAM_COMPARE
, left_param
, left_buf
, info_buf
);
1959 } END_FOR_EACH_PTR(link
);
1961 } END_FOR_EACH_SM(tmp
);
1964 static int parse_comparison(char **value
, int *op
)
1972 if (**value
== '=') {
1980 *op
= SPECIAL_EQUAL
;
1985 *op
= SPECIAL_NOTEQUAL
;
1989 if (**value
== '=') {
1998 if (**value
!= ' ') {
1999 sm_msg("internal error parsing comparison. %s", *value
);
2007 static int split_op_param_key(char *value
, int *op
, int *param
, char **key
)
2009 static char buf
[256];
2012 if (!parse_comparison(&value
, op
))
2015 snprintf(buf
, sizeof(buf
), value
);
2022 if (*param
< 0 || *param
> 99)
2034 static void db_return_comparison(struct expression
*expr
, int left_param
, char *key
, char *value
)
2036 struct expression
*left_arg
, *right_arg
;
2037 char *left_name
= NULL
;
2038 struct symbol
*left_sym
;
2039 char *right_name
= NULL
;
2040 struct symbol
*right_sym
;
2044 struct var_sym_list
*left_vsl
= NULL
, *right_vsl
= NULL
;
2046 if (left_param
== -1) {
2047 if (expr
->type
!= EXPR_ASSIGNMENT
)
2049 left_arg
= strip_expr(expr
->left
);
2051 while (expr
->type
== EXPR_ASSIGNMENT
)
2052 expr
= strip_expr(expr
->right
);
2053 if (expr
->type
!= EXPR_CALL
)
2056 while (expr
->type
== EXPR_ASSIGNMENT
)
2057 expr
= strip_expr(expr
->right
);
2058 if (expr
->type
!= EXPR_CALL
)
2061 left_arg
= get_argument_from_call_expr(expr
->args
, left_param
);
2066 if (!split_op_param_key(value
, &op
, &right_param
, &right_key
))
2069 right_arg
= get_argument_from_call_expr(expr
->args
, right_param
);
2073 left_name
= get_variable_from_key(left_arg
, key
, &left_sym
);
2074 if (!left_name
|| !left_sym
)
2077 right_name
= get_variable_from_key(right_arg
, right_key
, &right_sym
);
2078 if (!right_name
|| !right_sym
)
2081 add_var_sym(&left_vsl
, left_name
, left_sym
);
2082 add_var_sym(&right_vsl
, right_name
, right_sym
);
2084 add_comparison_var_sym(NULL
, left_name
, left_vsl
, op
, NULL
, right_name
, right_vsl
);
2087 free_string(left_name
);
2088 free_string(right_name
);
2091 int param_compare_limit_is_impossible(struct expression
*expr
, int left_param
, char *left_key
, char *value
)
2093 struct smatch_state
*state
;
2094 char *left_name
= NULL
;
2095 char *right_name
= NULL
;
2096 struct symbol
*left_sym
, *right_sym
;
2097 struct expression
*left_arg
, *right_arg
;
2104 while (expr
->type
== EXPR_ASSIGNMENT
)
2105 expr
= strip_expr(expr
->right
);
2106 if (expr
->type
!= EXPR_CALL
)
2109 if (!split_op_param_key(value
, &op
, &right_param
, &right_key
))
2112 left_arg
= get_argument_from_call_expr(expr
->args
, left_param
);
2116 right_arg
= get_argument_from_call_expr(expr
->args
, right_param
);
2120 left_name
= get_variable_from_key(left_arg
, left_key
, &left_sym
);
2121 right_name
= get_variable_from_key(right_arg
, right_key
, &right_sym
);
2122 if (!left_name
|| !right_name
)
2125 snprintf(buf
, sizeof(buf
), "%s vs %s", left_name
, right_name
);
2126 state
= get_state(compare_id
, buf
, NULL
);
2129 state_op
= state_to_comparison(state
);
2133 if (!filter_comparison(remove_unsigned_from_comparison(state_op
), op
))
2136 free_string(left_name
);
2137 free_string(right_name
);
2141 static void free_data(struct symbol
*sym
)
2145 clear_compare_data_alloc();
2148 void register_comparison(int id
)
2151 add_hook(&save_start_states
, AFTER_DEF_HOOK
);
2152 add_unmatched_state_hook(compare_id
, unmatched_comparison
);
2153 add_merge_hook(compare_id
, &merge_compare_states
);
2154 add_hook(&free_data
, AFTER_FUNC_HOOK
);
2155 add_hook(&match_call_info
, FUNCTION_CALL_HOOK
);
2156 add_split_return_callback(&print_return_comparison
);
2158 select_return_states_hook(PARAM_COMPARE
, &db_return_comparison
);
2161 void register_comparison_late(int id
)
2163 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
2166 void register_comparison_links(int id
)
2169 add_merge_hook(link_id
, &merge_links
);
2170 add_modification_hook(link_id
, &match_modify
);
2172 add_member_info_callback(link_id
, struct_member_callback
);
2175 void register_comparison_inc_dec(int id
)
2178 add_modification_hook_late(inc_dec_id
, &iter_modify
);
2181 void register_comparison_inc_dec_links(int id
)
2183 inc_dec_link_id
= id
;
2184 set_up_link_functions(inc_dec_id
, inc_dec_link_id
);
2187 static void filter_by_sm(struct sm_state
*sm
, int op
,
2188 struct state_list
**true_stack
,
2189 struct state_list
**false_stack
)
2191 struct compare_data
*data
;
2197 data
= sm
->state
->data
;
2200 filter_by_sm(sm
->left
, op
, true_stack
, false_stack
);
2201 filter_by_sm(sm
->right
, op
, true_stack
, false_stack
);
2206 if (data
->comparison
&&
2207 data
->comparison
== filter_comparison(data
->comparison
, op
))
2210 if (data
->comparison
&&
2211 data
->comparison
== filter_comparison(data
->comparison
, negate_comparison(op
)))
2215 add_ptr_list(true_stack
, sm
);
2217 add_ptr_list(false_stack
, sm
);
2220 filter_by_sm(sm
->left
, op
, true_stack
, false_stack
);
2221 filter_by_sm(sm
->right
, op
, true_stack
, false_stack
);
2225 struct sm_state
*comparison_implication_hook(struct expression
*expr
,
2226 struct state_list
**true_stack
,
2227 struct state_list
**false_stack
)
2229 struct sm_state
*sm
;
2232 static char buf
[256];
2234 if (expr
->type
!= EXPR_COMPARE
)
2239 left
= expr_to_var(expr
->left
);
2240 right
= expr_to_var(expr
->right
);
2241 if (!left
|| !right
) {
2247 if (strcmp(left
, right
) > 0) {
2252 op
= flip_comparison(op
);
2255 snprintf(buf
, sizeof(buf
), "%s vs %s", left
, right
);
2256 sm
= get_sm_state(compare_id
, buf
, NULL
);
2262 filter_by_sm(sm
, op
, true_stack
, false_stack
);
2263 if (!*true_stack
&& !*false_stack
)