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 static void add_comparison(struct expression
*left
, int comparison
, struct expression
*right
);
42 /* for handling for loops */
46 ALLOCATOR(compare_data
, "compare data");
48 static struct symbol
*vsl_to_sym(struct var_sym_list
*vsl
)
54 if (ptr_list_size((struct ptr_list
*)vsl
) != 1)
56 vs
= first_ptr_list((struct ptr_list
*)vsl
);
60 struct smatch_state
*alloc_compare_state(
61 struct expression
*left
,
62 const char *left_var
, struct var_sym_list
*left_vsl
,
64 struct expression
*right
,
65 const char *right_var
, struct var_sym_list
*right_vsl
)
67 struct smatch_state
*state
;
68 struct compare_data
*data
;
70 state
= __alloc_smatch_state(0);
71 state
->name
= alloc_sname(show_special(comparison
));
72 data
= __alloc_compare_data(0);
74 data
->left_var
= alloc_sname(left_var
);
75 data
->left_vsl
= clone_var_sym_list(left_vsl
);
76 data
->comparison
= comparison
;
78 data
->right_var
= alloc_sname(right_var
);
79 data
->right_vsl
= clone_var_sym_list(right_vsl
);
84 int state_to_comparison(struct smatch_state
*state
)
86 if (!state
|| !state
->data
)
88 return ((struct compare_data
*)state
->data
)->comparison
;
92 * flip_comparison() reverses the op left and right. So "x >= y" becomes "y <= x".
94 int flip_comparison(int op
)
101 case SPECIAL_UNSIGNED_LT
:
102 return SPECIAL_UNSIGNED_GT
;
105 case SPECIAL_UNSIGNED_LTE
:
106 return SPECIAL_UNSIGNED_GTE
;
108 return SPECIAL_EQUAL
;
109 case SPECIAL_NOTEQUAL
:
110 return SPECIAL_NOTEQUAL
;
113 case SPECIAL_UNSIGNED_GTE
:
114 return SPECIAL_UNSIGNED_LTE
;
117 case SPECIAL_UNSIGNED_GT
:
118 return SPECIAL_UNSIGNED_LT
;
120 sm_msg("internal smatch bug. unhandled comparison %d", op
);
125 int negate_comparison(int op
)
132 case SPECIAL_UNSIGNED_LT
:
133 return SPECIAL_UNSIGNED_GTE
;
136 case SPECIAL_UNSIGNED_LTE
:
137 return SPECIAL_UNSIGNED_GT
;
139 return SPECIAL_NOTEQUAL
;
140 case SPECIAL_NOTEQUAL
:
141 return SPECIAL_EQUAL
;
144 case SPECIAL_UNSIGNED_GTE
:
145 return SPECIAL_UNSIGNED_LT
;
148 case SPECIAL_UNSIGNED_GT
:
149 return SPECIAL_UNSIGNED_LTE
;
151 sm_msg("internal smatch bug. unhandled comparison %d", op
);
156 static int rl_comparison(struct range_list
*left_rl
, struct range_list
*right_rl
)
158 sval_t left_min
, left_max
, right_min
, right_max
;
159 struct symbol
*type
= &int_ctype
;
161 if (!left_rl
|| !right_rl
)
164 if (type_positive_bits(rl_type(left_rl
)) > type_positive_bits(type
))
165 type
= rl_type(left_rl
);
166 if (type_positive_bits(rl_type(right_rl
)) > type_positive_bits(type
))
167 type
= rl_type(right_rl
);
169 left_rl
= cast_rl(type
, left_rl
);
170 right_rl
= cast_rl(type
, right_rl
);
172 left_min
= rl_min(left_rl
);
173 left_max
= rl_max(left_rl
);
174 right_min
= rl_min(right_rl
);
175 right_max
= rl_max(right_rl
);
177 if (left_min
.value
== left_max
.value
&&
178 right_min
.value
== right_max
.value
&&
179 left_min
.value
== right_min
.value
)
180 return SPECIAL_EQUAL
;
182 if (sval_cmp(left_max
, right_min
) < 0)
184 if (sval_cmp(left_max
, right_min
) == 0)
186 if (sval_cmp(left_min
, right_max
) > 0)
188 if (sval_cmp(left_min
, right_max
) == 0)
194 static int comparison_from_extra(struct expression
*a
, struct expression
*b
)
196 struct range_list
*left
, *right
;
198 if (!get_implied_rl(a
, &left
))
200 if (!get_implied_rl(b
, &right
))
203 return rl_comparison(left
, right
);
206 static struct range_list
*get_orig_rl(struct var_sym_list
*vsl
)
209 struct smatch_state
*state
;
213 sym
= vsl_to_sym(vsl
);
214 if (!sym
|| !sym
->ident
)
216 state
= get_orig_estate(sym
->ident
->name
, sym
);
217 return estate_rl(state
);
220 static struct smatch_state
*unmatched_comparison(struct sm_state
*sm
)
222 struct compare_data
*data
= sm
->state
->data
;
223 struct range_list
*left_rl
, *right_rl
;
229 if (strstr(data
->left_var
, " orig"))
230 left_rl
= get_orig_rl(data
->left_vsl
);
231 else if (!get_implied_rl_var_sym(data
->left_var
, vsl_to_sym(data
->left_vsl
), &left_rl
))
234 if (strstr(data
->right_var
, " orig"))
235 right_rl
= get_orig_rl(data
->right_vsl
);
236 else if (!get_implied_rl_var_sym(data
->right_var
, vsl_to_sym(data
->right_vsl
), &right_rl
))
239 op
= rl_comparison(left_rl
, right_rl
);
241 return alloc_compare_state(
242 data
->left
, data
->left_var
, data
->left_vsl
,
244 data
->right
, data
->right_var
, data
->right_vsl
);
249 /* remove_unsigned_from_comparison() is obviously a hack. */
250 int remove_unsigned_from_comparison(int op
)
253 case SPECIAL_UNSIGNED_LT
:
255 case SPECIAL_UNSIGNED_LTE
:
257 case SPECIAL_UNSIGNED_GTE
:
259 case SPECIAL_UNSIGNED_GT
:
267 * This is for when you merge states "a < b" and "a == b", the result is that
268 * we can say for sure, "a <= b" after the merge.
270 int merge_comparisons(int one
, int two
)
277 one
= remove_unsigned_from_comparison(one
);
278 two
= remove_unsigned_from_comparison(two
);
328 return SPECIAL_NOTEQUAL
;
339 * This is for if you have "a < b" and "b <= c". Or in other words,
340 * "a < b <= c". You would call this like get_combined_comparison('<', '<=').
341 * The return comparison would be '<'.
343 * This function is different from merge_comparisons(), for example:
344 * merge_comparison('<', '==') returns '<='
345 * get_combined_comparison('<', '==') returns '<'
347 int combine_comparisons(int left_compare
, int right_compare
)
351 left_compare
= remove_unsigned_from_comparison(left_compare
);
352 right_compare
= remove_unsigned_from_comparison(right_compare
);
356 switch (left_compare
) {
365 return right_compare
;
374 switch (right_compare
) {
406 int filter_comparison(int orig
, int op
)
411 orig
= remove_unsigned_from_comparison(orig
);
412 op
= remove_unsigned_from_comparison(op
);
421 case SPECIAL_NOTEQUAL
:
431 case SPECIAL_NOTEQUAL
:
440 case SPECIAL_UNSIGNED_LTE
:
441 case SPECIAL_UNSIGNED_GTE
:
442 return SPECIAL_EQUAL
;
445 case SPECIAL_NOTEQUAL
:
450 case SPECIAL_UNSIGNED_LT
:
451 case SPECIAL_UNSIGNED_LTE
:
452 return SPECIAL_UNSIGNED_LT
;
453 case SPECIAL_NOTEQUAL
:
458 case SPECIAL_UNSIGNED_GT
:
459 case SPECIAL_UNSIGNED_GTE
:
460 return SPECIAL_UNSIGNED_GT
;
466 return SPECIAL_EQUAL
;
471 case SPECIAL_NOTEQUAL
:
479 case SPECIAL_NOTEQUAL
:
483 case SPECIAL_UNSIGNED_LT
:
485 case SPECIAL_UNSIGNED_LT
:
486 case SPECIAL_UNSIGNED_LTE
:
487 case SPECIAL_NOTEQUAL
:
488 return SPECIAL_UNSIGNED_LT
;
491 case SPECIAL_UNSIGNED_LTE
:
493 case SPECIAL_UNSIGNED_LT
:
494 case SPECIAL_UNSIGNED_LTE
:
497 case SPECIAL_NOTEQUAL
:
498 return SPECIAL_UNSIGNED_LT
;
499 case SPECIAL_UNSIGNED_GTE
:
500 return SPECIAL_EQUAL
;
503 case SPECIAL_UNSIGNED_GTE
:
505 case SPECIAL_UNSIGNED_LTE
:
506 return SPECIAL_EQUAL
;
507 case SPECIAL_NOTEQUAL
:
508 return SPECIAL_UNSIGNED_GT
;
510 case SPECIAL_UNSIGNED_GTE
:
511 case SPECIAL_UNSIGNED_GT
:
515 case SPECIAL_UNSIGNED_GT
:
517 case SPECIAL_UNSIGNED_GT
:
518 case SPECIAL_UNSIGNED_GTE
:
519 case SPECIAL_NOTEQUAL
:
520 return SPECIAL_UNSIGNED_GT
;
527 static void pre_merge_hook(struct sm_state
*sm
)
529 struct compare_data
*data
= sm
->state
->data
;
534 other
= get_comparison(data
->left
, data
->right
);
538 set_state(compare_id
, sm
->name
, NULL
,
539 alloc_compare_state(data
->left
, data
->left_var
, data
->left_vsl
,
541 data
->right
, data
->right_var
, data
->right_vsl
));
544 struct smatch_state
*merge_compare_states(struct smatch_state
*s1
, struct smatch_state
*s2
)
546 struct compare_data
*data
= s1
->data
;
549 op
= merge_comparisons(state_to_comparison(s1
), state_to_comparison(s2
));
551 return alloc_compare_state(
552 data
->left
, data
->left_var
, data
->left_vsl
,
554 data
->right
, data
->right_var
, data
->right_vsl
);
558 static struct smatch_state
*alloc_link_state(struct string_list
*links
)
560 struct smatch_state
*state
;
561 static char buf
[256];
565 state
= __alloc_smatch_state(0);
568 FOR_EACH_PTR(links
, tmp
) {
570 snprintf(buf
, sizeof(buf
), "%s", tmp
);
572 append(buf
, ", ", sizeof(buf
));
573 append(buf
, tmp
, sizeof(buf
));
575 } END_FOR_EACH_PTR(tmp
);
577 state
->name
= alloc_sname(buf
);
582 static void save_start_states(struct statement
*stmt
)
584 struct symbol
*param
;
586 char state_name
[128];
587 struct smatch_state
*state
;
588 struct string_list
*links
;
591 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
592 struct var_sym_list
*left_vsl
= NULL
;
593 struct var_sym_list
*right_vsl
= NULL
;
597 snprintf(orig
, sizeof(orig
), "%s orig", param
->ident
->name
);
598 snprintf(state_name
, sizeof(state_name
), "%s vs %s", param
->ident
->name
, orig
);
599 add_var_sym(&left_vsl
, param
->ident
->name
, param
);
600 add_var_sym(&right_vsl
, orig
, param
);
601 state
= alloc_compare_state(
602 NULL
, param
->ident
->name
, left_vsl
,
604 NULL
, alloc_sname(orig
), right_vsl
);
605 set_state(compare_id
, state_name
, NULL
, state
);
607 link
= alloc_sname(state_name
);
609 insert_string(&links
, link
);
610 state
= alloc_link_state(links
);
611 set_state(link_id
, param
->ident
->name
, param
, state
);
612 } END_FOR_EACH_PTR(param
);
615 static struct smatch_state
*merge_links(struct smatch_state
*s1
, struct smatch_state
*s2
)
617 struct smatch_state
*ret
;
618 struct string_list
*links
;
620 links
= combine_string_lists(s1
->data
, s2
->data
);
621 ret
= alloc_link_state(links
);
625 static void save_link_var_sym(const char *var
, struct symbol
*sym
, const char *link
)
627 struct smatch_state
*old_state
, *new_state
;
628 struct string_list
*links
;
631 old_state
= get_state(link_id
, var
, sym
);
633 links
= clone_str_list(old_state
->data
);
637 new = alloc_sname(link
);
638 insert_string(&links
, new);
640 new_state
= alloc_link_state(links
);
641 set_state(link_id
, var
, sym
, new_state
);
644 static void match_inc(struct sm_state
*sm
)
646 struct string_list
*links
;
647 struct smatch_state
*state
, *new;
648 struct compare_data
*data
;
653 links
= sm
->state
->data
;
655 FOR_EACH_PTR(links
, tmp
) {
656 state
= get_state(compare_id
, tmp
, NULL
);
664 if (strncmp(sm
->name
, tmp
, strlen(sm
->name
)) != 0 ||
665 tmp
[strlen(sm
->name
)] != ' ')
668 op
= state_to_comparison(state
);
670 switch (flip
? flip_comparison(op
) : op
) {
673 case SPECIAL_UNSIGNED_GTE
:
675 case SPECIAL_UNSIGNED_GT
:
676 new = alloc_compare_state(
677 data
->left
, data
->left_var
, data
->left_vsl
,
679 data
->right
, data
->right_var
, data
->right_vsl
);
680 set_state(compare_id
, tmp
, NULL
, new);
683 case SPECIAL_UNSIGNED_LT
:
684 new = alloc_compare_state(
685 data
->left
, data
->left_var
, data
->left_vsl
,
686 flip
? SPECIAL_GTE
: SPECIAL_LTE
,
687 data
->right
, data
->right_var
, data
->right_vsl
);
688 set_state(compare_id
, tmp
, NULL
, new);
691 set_state(compare_id
, tmp
, NULL
, &undefined
);
693 } END_FOR_EACH_PTR(tmp
);
696 static void match_dec(struct sm_state
*sm
)
698 struct string_list
*links
;
699 struct smatch_state
*state
;
702 links
= sm
->state
->data
;
704 FOR_EACH_PTR(links
, tmp
) {
705 state
= get_state(compare_id
, tmp
, NULL
);
707 switch (state_to_comparison(state
)) {
710 case SPECIAL_UNSIGNED_LTE
:
712 case SPECIAL_UNSIGNED_LT
: {
713 struct compare_data
*data
= state
->data
;
714 struct smatch_state
*new;
716 new = alloc_compare_state(
717 data
->left
, data
->left_var
, data
->left_vsl
,
719 data
->right
, data
->right_var
, data
->right_vsl
);
720 set_state(compare_id
, tmp
, NULL
, new);
724 set_state(compare_id
, tmp
, NULL
, &undefined
);
726 } END_FOR_EACH_PTR(tmp
);
729 static void match_inc_dec(struct sm_state
*sm
, struct expression
*mod_expr
)
732 * if (foo > bar) then ++foo is also > bar.
736 if (mod_expr
->type
!= EXPR_PREOP
&& mod_expr
->type
!= EXPR_POSTOP
)
739 if (mod_expr
->op
== SPECIAL_INCREMENT
)
741 else if (mod_expr
->op
== SPECIAL_DECREMENT
)
745 static int is_self_assign(struct expression
*expr
)
747 if (!expr
|| expr
->type
!= EXPR_ASSIGNMENT
|| expr
->op
!= '=')
749 return expr_equiv(expr
->left
, expr
->right
);
752 static void match_modify(struct sm_state
*sm
, struct expression
*mod_expr
)
754 struct string_list
*links
;
757 if (mod_expr
&& is_self_assign(mod_expr
))
760 /* handled by match_inc_dec() */
762 ((mod_expr
->type
== EXPR_PREOP
|| mod_expr
->type
== EXPR_POSTOP
) &&
763 (mod_expr
->op
== SPECIAL_INCREMENT
|| mod_expr
->op
== SPECIAL_DECREMENT
)))
766 links
= sm
->state
->data
;
768 FOR_EACH_PTR(links
, tmp
) {
769 set_state(compare_id
, tmp
, NULL
, &undefined
);
770 } END_FOR_EACH_PTR(tmp
);
771 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
774 static void match_preop(struct expression
*expr
)
776 struct expression
*parent
;
777 struct range_list
*left
, *right
;
781 * This is an important special case. Say you have:
785 * Assume that we know the range of limit is higher than the start
786 * value for "j". Then the first thing that we process is the ++j. We
787 * have not comparison states set up so it doesn't get caught by the
788 * modification hook. But it does get caught by smatch_extra which sets
789 * j to unknown then we parse the "j == limit" and sets false to != but
790 * really we want false to be <.
792 * So what we do is we set j < limit here, then the match_modify catches
793 * it and we do a match_inc_dec().
797 if (expr
->type
!= EXPR_PREOP
||
798 (expr
->op
!= SPECIAL_INCREMENT
&& expr
->op
!= SPECIAL_DECREMENT
))
801 parent
= expr_get_parent_expr(expr
);
804 if (parent
->type
!= EXPR_COMPARE
|| parent
->op
!= SPECIAL_EQUAL
)
806 if (parent
->left
!= expr
)
809 if (!get_implied_rl(expr
->unop
, &left
) ||
810 !get_implied_rl(parent
->right
, &right
))
813 op
= rl_comparison(left
, right
);
817 add_comparison(expr
->unop
, op
, parent
->right
);
820 static char *chunk_to_var_sym(struct expression
*expr
, struct symbol
**sym
)
822 expr
= strip_expr(expr
);
828 if (expr
->type
== EXPR_PREOP
&&
829 (expr
->op
== SPECIAL_INCREMENT
||
830 expr
->op
== SPECIAL_DECREMENT
))
831 expr
= strip_expr(expr
->unop
);
833 if (expr
->type
== EXPR_CALL
) {
836 snprintf(buf
, sizeof(buf
), "return %p", expr
);
837 return alloc_string(buf
);
840 return expr_to_chunk_sym_vsl(expr
, sym
, NULL
);
843 static char *chunk_to_var(struct expression
*expr
)
845 return chunk_to_var_sym(expr
, NULL
);
848 static struct smatch_state
*get_state_chunk(int owner
, struct expression
*expr
)
852 struct smatch_state
*ret
;
854 name
= chunk_to_var_sym(expr
, &sym
);
858 ret
= get_state(owner
, name
, sym
);
863 static void save_link(struct expression
*expr
, char *link
)
868 expr
= strip_expr(expr
);
869 if (expr
->type
== EXPR_BINOP
) {
872 chunk
= chunk_to_var(expr
);
876 save_link(expr
->left
, link
);
877 save_link(expr
->right
, link
);
878 save_link_var_sym(chunk
, NULL
, link
);
882 var
= chunk_to_var_sym(expr
, &sym
);
886 save_link_var_sym(var
, sym
, link
);
890 static int get_orig_comparison(struct stree
*pre_stree
, const char *left
, const char *right
)
892 struct smatch_state
*state
;
893 struct compare_data
*data
;
895 char state_name
[256];
897 if (strcmp(left
, right
) > 0) {
898 const char *tmp
= right
;
905 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
906 state
= get_state_stree(pre_stree
, compare_id
, state_name
, NULL
);
907 if (!state
|| !state
->data
)
911 return flip_comparison(data
->comparison
);
912 return data
->comparison
;
916 static int have_common_var_sym(struct var_sym_list
*left_vsl
, struct var_sym_list
*right_vsl
)
920 FOR_EACH_PTR(left_vsl
, tmp
) {
921 if (in_var_sym_list(right_vsl
, tmp
->var
, tmp
->sym
))
923 } END_FOR_EACH_PTR(tmp
);
929 * The idea here is that we take a comparison "a < b" and then we look at all
930 * the things which "b" is compared against "b < c" and we say that that implies
931 * a relationship "a < c".
933 * The names here about because the comparisons are organized like this
937 static void update_tf_links(struct stree
*pre_stree
,
938 struct expression
*left_expr
,
939 const char *left_var
, struct var_sym_list
*left_vsl
,
940 int left_comparison
, int left_false_comparison
,
941 const char *mid_var
, struct var_sym_list
*mid_vsl
,
942 struct string_list
*links
)
944 struct smatch_state
*state
;
945 struct smatch_state
*true_state
, *false_state
;
946 struct compare_data
*data
;
947 struct expression
*right_expr
;
948 const char *right_var
;
949 struct var_sym_list
*right_vsl
;
951 int right_comparison
;
953 int false_comparison
;
955 char state_name
[256];
958 FOR_EACH_PTR(links
, tmp
) {
959 state
= get_state_stree(pre_stree
, compare_id
, tmp
, NULL
);
960 if (!state
|| !state
->data
)
963 right_comparison
= data
->comparison
;
964 right_expr
= data
->right
;
965 right_var
= data
->right_var
;
966 right_vsl
= data
->right_vsl
;
967 if (strcmp(mid_var
, right_var
) == 0) {
968 right_expr
= data
->left
;
969 right_var
= data
->left_var
;
970 right_vsl
= data
->left_vsl
;
971 right_comparison
= flip_comparison(right_comparison
);
973 if (have_common_var_sym(left_vsl
, right_vsl
))
976 orig_comparison
= get_orig_comparison(pre_stree
, left_var
, right_var
);
978 true_comparison
= combine_comparisons(left_comparison
, right_comparison
);
979 false_comparison
= combine_comparisons(left_false_comparison
, right_comparison
);
981 true_comparison
= filter_comparison(orig_comparison
, true_comparison
);
982 false_comparison
= filter_comparison(orig_comparison
, false_comparison
);
984 if (strcmp(left_var
, right_var
) > 0) {
985 struct expression
*tmp_expr
= left_expr
;
986 const char *tmp_var
= left_var
;
987 struct var_sym_list
*tmp_vsl
= left_vsl
;
989 left_expr
= right_expr
;
990 left_var
= right_var
;
991 left_vsl
= right_vsl
;
992 right_expr
= tmp_expr
;
995 true_comparison
= flip_comparison(true_comparison
);
996 false_comparison
= flip_comparison(false_comparison
);
999 if (!true_comparison
&& !false_comparison
)
1002 if (true_comparison
)
1003 true_state
= alloc_compare_state(
1004 left_expr
, left_var
, left_vsl
,
1006 right_expr
, right_var
, right_vsl
);
1009 if (false_comparison
)
1010 false_state
= alloc_compare_state(
1011 left_expr
, left_var
, left_vsl
,
1013 right_expr
, right_var
, right_vsl
);
1017 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_var
, right_var
);
1018 set_true_false_states(compare_id
, state_name
, NULL
, true_state
, false_state
);
1019 FOR_EACH_PTR(left_vsl
, vs
) {
1020 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
1021 } END_FOR_EACH_PTR(vs
);
1022 FOR_EACH_PTR(right_vsl
, vs
) {
1023 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
1024 } END_FOR_EACH_PTR(vs
);
1025 if (!vsl_to_sym(left_vsl
))
1026 save_link_var_sym(left_var
, NULL
, state_name
);
1027 if (!vsl_to_sym(right_vsl
))
1028 save_link_var_sym(right_var
, NULL
, state_name
);
1029 } END_FOR_EACH_PTR(tmp
);
1032 static void update_tf_data(struct stree
*pre_stree
,
1033 struct expression
*left_expr
,
1034 const char *left_name
, struct var_sym_list
*left_vsl
,
1035 struct expression
*right_expr
,
1036 const char *right_name
, struct var_sym_list
*right_vsl
,
1037 int true_comparison
, int false_comparison
)
1039 struct smatch_state
*state
;
1041 state
= get_state_stree(pre_stree
, link_id
, right_name
, vsl_to_sym(right_vsl
));
1043 update_tf_links(pre_stree
, left_expr
, left_name
, left_vsl
, true_comparison
, false_comparison
, right_name
, right_vsl
, state
->data
);
1045 state
= get_state_stree(pre_stree
, link_id
, left_name
, vsl_to_sym(left_vsl
));
1047 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
);
1050 static void iter_modify(struct sm_state
*sm
, struct expression
*mod_expr
)
1052 if (sm
->state
!= &start
||
1054 (mod_expr
->type
!= EXPR_PREOP
&& mod_expr
->type
!= EXPR_POSTOP
) ||
1055 mod_expr
->op
!= SPECIAL_INCREMENT
)
1056 set_state(inc_dec_id
, sm
->name
, sm
->sym
, &undefined
);
1058 set_state(inc_dec_id
, sm
->name
, sm
->sym
, &incremented
);
1061 static void handle_for_loops(struct expression
*expr
, char *state_name
, struct smatch_state
*false_state
)
1064 char *iter_name
, *cap_name
;
1065 struct symbol
*iter_sym
, *cap_sym
;
1066 struct compare_data
*data
;
1068 if (expr
->op
!= '<' && expr
->op
!= SPECIAL_UNSIGNED_LT
)
1071 if (!__cur_stmt
|| !__prev_stmt
)
1073 if (__cur_stmt
->type
!= STMT_ITERATOR
)
1075 if (__cur_stmt
->iterator_pre_condition
!= expr
)
1078 /* literals are handled in smatch_extra.c */
1079 if (get_value(expr
->right
, &sval
))
1082 /* First time checking the condition */
1083 if (__prev_stmt
== __cur_stmt
->iterator_pre_statement
) {
1084 if (!get_implied_value(expr
->left
, &sval
) ||
1088 iter_name
= expr_to_var_sym(expr
->left
, &iter_sym
);
1089 cap_name
= expr_to_var_sym(expr
->right
, &cap_sym
);
1090 if (!iter_name
|| !cap_name
|| !iter_sym
|| !cap_sym
) {
1091 free_string(iter_name
);
1092 free_string(cap_name
);
1096 set_state(inc_dec_id
, iter_name
, iter_sym
, &start
);
1097 store_link(inc_dec_link_id
, cap_name
, cap_sym
, iter_name
, iter_sym
);
1099 free_string(iter_name
);
1100 free_string(cap_name
);
1104 /* Second time checking the condtion */
1105 if (__prev_stmt
!= __cur_stmt
->iterator_post_statement
)
1108 if (get_state_chunk(inc_dec_id
, expr
->left
) != &incremented
)
1111 data
= false_state
->data
;
1112 false_state
= alloc_compare_state(
1113 data
->left
, data
->left_var
, data
->left_vsl
,
1115 data
->right
, data
->right_var
, data
->right_vsl
);
1117 set_true_false_states(compare_id
, state_name
, NULL
, NULL
, false_state
);
1120 static int is_plus_one(struct expression
*expr
)
1124 if (expr
->type
!= EXPR_BINOP
|| expr
->op
!= '+')
1126 if (!get_implied_value(expr
->right
, &sval
) || sval
.value
!= 1)
1131 static int is_minus_one(struct expression
*expr
)
1135 if (expr
->type
!= EXPR_BINOP
|| expr
->op
!= '-')
1137 if (!get_implied_value(expr
->right
, &sval
) || sval
.value
!= 1)
1142 static void move_plus_to_minus_helper(struct expression
**left_p
, struct expression
**right_p
)
1144 struct expression
*left
= *left_p
;
1145 struct expression
*right
= *right_p
;
1148 * These two are basically equivalent: "foo + 1 != bar" and
1149 * "foo != bar - 1". There are issues with signedness and integer
1150 * overflows. There are also issues with type as well. But let's
1151 * pretend we can ignore all that stuff for now.
1155 if (!is_plus_one(left
))
1158 *left_p
= left
->left
;
1159 *right_p
= binop_expression(right
, '-', left
->right
);
1162 static void move_plus_to_minus(struct expression
**left_p
, struct expression
**right_p
)
1164 if (is_plus_one(*left_p
) && is_plus_one(*right_p
))
1167 move_plus_to_minus_helper(left_p
, right_p
);
1168 move_plus_to_minus_helper(right_p
, left_p
);
1171 static void handle_comparison(struct expression
*left_expr
, int op
, struct expression
*right_expr
, char **_state_name
, struct smatch_state
**_false_state
)
1175 struct symbol
*left_sym
, *right_sym
;
1176 struct var_sym_list
*left_vsl
= NULL
;
1177 struct var_sym_list
*right_vsl
= NULL
;
1179 int orig_comparison
;
1180 struct smatch_state
*true_state
, *false_state
;
1181 static char state_name
[256];
1182 struct stree
*pre_stree
;
1185 left_expr
= strip_parens(left_expr
);
1186 right_expr
= strip_parens(right_expr
);
1188 false_op
= negate_comparison(op
);
1190 move_plus_to_minus(&left_expr
, &right_expr
);
1192 if (op
== SPECIAL_UNSIGNED_LT
&&
1193 get_implied_value(left_expr
, &sval
) &&
1195 false_op
= SPECIAL_EQUAL
;
1197 if (op
== SPECIAL_UNSIGNED_GT
&&
1198 get_implied_value(right_expr
, &sval
) &&
1200 false_op
= SPECIAL_EQUAL
;
1202 left
= chunk_to_var_sym(left_expr
, &left_sym
);
1206 add_var_sym(&left_vsl
, left
, left_sym
);
1208 left_vsl
= expr_to_vsl(left_expr
);
1209 right
= chunk_to_var_sym(right_expr
, &right_sym
);
1213 add_var_sym(&right_vsl
, right
, right_sym
);
1215 right_vsl
= expr_to_vsl(right_expr
);
1217 if (strcmp(left
, right
) > 0) {
1218 char *tmp_name
= left
;
1219 struct var_sym_list
*tmp_vsl
= left_vsl
;
1220 struct expression
*tmp_expr
= left_expr
;
1223 left_vsl
= right_vsl
;
1224 left_expr
= right_expr
;
1226 right_vsl
= tmp_vsl
;
1227 right_expr
= tmp_expr
;
1228 op
= flip_comparison(op
);
1229 false_op
= flip_comparison(false_op
);
1232 orig_comparison
= get_comparison(left_expr
, right_expr
);
1233 op
= filter_comparison(orig_comparison
, op
);
1234 false_op
= filter_comparison(orig_comparison
, false_op
);
1236 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
1237 true_state
= alloc_compare_state(
1238 left_expr
, left
, left_vsl
,
1240 right_expr
, right
, right_vsl
);
1241 false_state
= alloc_compare_state(
1242 left_expr
, left
, left_vsl
,
1244 right_expr
, right
, right_vsl
);
1246 pre_stree
= clone_stree(__get_cur_stree());
1247 update_tf_data(pre_stree
, left_expr
, left
, left_vsl
, right_expr
, right
, right_vsl
, op
, false_op
);
1248 free_stree(&pre_stree
);
1250 set_true_false_states(compare_id
, state_name
, NULL
, true_state
, false_state
);
1251 __compare_param_limit_hook(left_expr
, right_expr
, state_name
, true_state
, false_state
);
1252 save_link(left_expr
, state_name
);
1253 save_link(right_expr
, state_name
);
1256 *_false_state
= false_state
;
1258 *_state_name
= state_name
;
1264 void __comparison_match_condition(struct expression
*expr
)
1266 struct expression
*left
, *right
, *new_left
, *new_right
, *tmp
;
1267 struct smatch_state
*false_state
= NULL
;
1268 char *state_name
= NULL
;
1271 if (expr
->type
!= EXPR_COMPARE
)
1274 handle_comparison(expr
->left
, expr
->op
, expr
->right
, &state_name
, &false_state
);
1275 if (false_state
&& state_name
)
1276 handle_for_loops(expr
, state_name
, false_state
);
1278 left
= strip_parens(expr
->left
);
1279 right
= strip_parens(expr
->right
);
1281 if (left
->type
== EXPR_BINOP
&& left
->op
== '+') {
1282 new_left
= left
->left
;
1283 new_right
= binop_expression(right
, '-', left
->right
);
1284 handle_comparison(new_left
, expr
->op
, new_right
, NULL
, NULL
);
1286 new_left
= left
->right
;
1287 new_right
= binop_expression(right
, '-', left
->left
);
1288 handle_comparison(new_left
, expr
->op
, new_right
, NULL
, NULL
);
1293 left
= strip_parens(expr
->left
);
1294 right
= strip_parens(expr
->right
);
1295 if (get_last_expr_from_expression_stmt(expr
->left
)) {
1296 left
= get_last_expr_from_expression_stmt(expr
->left
);
1299 if (get_last_expr_from_expression_stmt(expr
->right
)) {
1300 right
= get_last_expr_from_expression_stmt(expr
->right
);
1308 while ((tmp
= get_assigned_expr(left
))) {
1311 left
= strip_expr(tmp
);
1314 while ((tmp
= get_assigned_expr(right
))) {
1317 right
= strip_expr(tmp
);
1320 handle_comparison(left
, expr
->op
, right
, NULL
, NULL
);
1323 static void add_comparison_var_sym(
1324 struct expression
*left_expr
,
1325 const char *left_name
, struct var_sym_list
*left_vsl
,
1327 struct expression
*right_expr
,
1328 const char *right_name
, struct var_sym_list
*right_vsl
)
1330 struct smatch_state
*state
;
1332 char state_name
[256];
1334 if (strcmp(left_name
, right_name
) > 0) {
1335 struct expression
*tmp_expr
= left_expr
;
1336 const char *tmp_name
= left_name
;
1337 struct var_sym_list
*tmp_vsl
= left_vsl
;
1339 left_expr
= right_expr
;
1340 left_name
= right_name
;
1341 left_vsl
= right_vsl
;
1342 right_expr
= tmp_expr
;
1343 right_name
= tmp_name
;
1344 right_vsl
= tmp_vsl
;
1345 comparison
= flip_comparison(comparison
);
1347 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_name
, right_name
);
1348 state
= alloc_compare_state(
1349 left_expr
, left_name
, left_vsl
,
1351 right_expr
, right_name
, right_vsl
);
1353 set_state(compare_id
, state_name
, NULL
, state
);
1355 FOR_EACH_PTR(left_vsl
, vs
) {
1356 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
1357 } END_FOR_EACH_PTR(vs
);
1358 FOR_EACH_PTR(right_vsl
, vs
) {
1359 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
1360 } END_FOR_EACH_PTR(vs
);
1363 static void add_comparison(struct expression
*left
, int comparison
, struct expression
*right
)
1365 char *left_name
= NULL
;
1366 char *right_name
= NULL
;
1367 struct symbol
*left_sym
, *right_sym
;
1368 struct var_sym_list
*left_vsl
, *right_vsl
;
1369 struct smatch_state
*state
;
1370 char state_name
[256];
1372 left_name
= chunk_to_var_sym(left
, &left_sym
);
1375 left_vsl
= expr_to_vsl(left
);
1376 right_name
= chunk_to_var_sym(right
, &right_sym
);
1379 right_vsl
= expr_to_vsl(right
);
1381 if (strcmp(left_name
, right_name
) > 0) {
1382 struct expression
*tmp_expr
= left
;
1383 struct symbol
*tmp_sym
= left_sym
;
1384 char *tmp_name
= left_name
;
1385 struct var_sym_list
*tmp_vsl
= left_vsl
;
1388 left_name
= right_name
;
1389 left_sym
= right_sym
;
1390 left_vsl
= right_vsl
;
1392 right_name
= tmp_name
;
1393 right_sym
= tmp_sym
;
1394 right_vsl
= tmp_vsl
;
1395 comparison
= flip_comparison(comparison
);
1397 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_name
, right_name
);
1398 state
= alloc_compare_state(
1399 left
, left_name
, left_vsl
,
1401 right
, right_name
, right_vsl
);
1403 set_state(compare_id
, state_name
, NULL
, state
);
1404 save_link(left
, state_name
);
1405 save_link(right
, state_name
);
1408 free_string(left_name
);
1409 free_string(right_name
);
1412 static void match_assign_add(struct expression
*expr
)
1414 struct expression
*right
;
1415 struct expression
*r_left
, *r_right
;
1416 sval_t left_tmp
, right_tmp
;
1418 right
= strip_expr(expr
->right
);
1419 r_left
= strip_expr(right
->left
);
1420 r_right
= strip_expr(right
->right
);
1422 get_absolute_min(r_left
, &left_tmp
);
1423 get_absolute_min(r_right
, &right_tmp
);
1425 if (left_tmp
.value
> 0)
1426 add_comparison(expr
->left
, '>', r_right
);
1427 else if (left_tmp
.value
== 0)
1428 add_comparison(expr
->left
, SPECIAL_GTE
, r_right
);
1430 if (right_tmp
.value
> 0)
1431 add_comparison(expr
->left
, '>', r_left
);
1432 else if (right_tmp
.value
== 0)
1433 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
1436 static void match_assign_sub(struct expression
*expr
)
1438 struct expression
*right
;
1439 struct expression
*r_left
, *r_right
;
1443 right
= strip_expr(expr
->right
);
1444 r_left
= strip_expr(right
->left
);
1445 r_right
= strip_expr(right
->right
);
1447 if (get_absolute_min(r_right
, &min
) && sval_is_negative(min
))
1450 comparison
= get_comparison(r_left
, r_right
);
1452 switch (comparison
) {
1455 if (implied_not_equal(r_right
, 0))
1456 add_comparison(expr
->left
, '>', r_left
);
1458 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
1463 static void match_assign_divide(struct expression
*expr
)
1465 struct expression
*right
;
1466 struct expression
*r_left
, *r_right
;
1469 right
= strip_expr(expr
->right
);
1470 r_left
= strip_expr(right
->left
);
1471 r_right
= strip_expr(right
->right
);
1472 if (!get_implied_min(r_right
, &min
) || min
.value
<= 1)
1475 add_comparison(expr
->left
, '<', r_left
);
1478 static void match_binop_assign(struct expression
*expr
)
1480 struct expression
*right
;
1482 right
= strip_expr(expr
->right
);
1483 if (right
->op
== '+')
1484 match_assign_add(expr
);
1485 if (right
->op
== '-')
1486 match_assign_sub(expr
);
1487 if (right
->op
== '/')
1488 match_assign_divide(expr
);
1491 static void copy_comparisons(struct expression
*left
, struct expression
*right
)
1493 struct string_list
*links
;
1494 struct smatch_state
*state
;
1495 struct compare_data
*data
;
1496 struct symbol
*left_sym
, *right_sym
;
1497 char *left_var
= NULL
;
1498 char *right_var
= NULL
;
1499 struct var_sym_list
*left_vsl
;
1500 struct expression
*expr
;
1502 struct var_sym_list
*vsl
;
1506 left_var
= chunk_to_var_sym(left
, &left_sym
);
1509 left_vsl
= expr_to_vsl(left
);
1510 right_var
= chunk_to_var_sym(right
, &right_sym
);
1514 state
= get_state(link_id
, right_var
, right_sym
);
1517 links
= state
->data
;
1519 FOR_EACH_PTR(links
, tmp
) {
1520 state
= get_state(compare_id
, tmp
, NULL
);
1521 if (!state
|| !state
->data
)
1524 comparison
= data
->comparison
;
1526 var
= data
->right_var
;
1527 vsl
= data
->right_vsl
;
1528 if (strcmp(var
, right_var
) == 0) {
1530 var
= data
->left_var
;
1531 vsl
= data
->left_vsl
;
1532 comparison
= flip_comparison(comparison
);
1534 /* n = copy_from_user(dest, src, n); leads to n <= n which is nonsense */
1535 if (strcmp(left_var
, var
) == 0)
1537 add_comparison_var_sym(left
, left_var
, left_vsl
, comparison
, expr
, var
, vsl
);
1538 } END_FOR_EACH_PTR(tmp
);
1541 free_string(right_var
);
1544 static void match_assign(struct expression
*expr
)
1546 struct expression
*right
;
1548 if (expr
->op
!= '=')
1550 if (__in_fake_assign
|| outside_of_function())
1553 if (is_struct(expr
->left
))
1556 if (is_self_assign(expr
))
1559 copy_comparisons(expr
->left
, expr
->right
);
1560 add_comparison(expr
->left
, SPECIAL_EQUAL
, expr
->right
);
1562 right
= strip_expr(expr
->right
);
1563 if (right
->type
== EXPR_BINOP
)
1564 match_binop_assign(expr
);
1567 int get_comparison_strings(const char *one
, const char *two
)
1570 struct smatch_state
*state
;
1577 if (strcmp(one
, two
) == 0)
1578 return SPECIAL_EQUAL
;
1580 if (strcmp(one
, two
) > 0) {
1581 const char *tmp
= one
;
1588 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
1589 state
= get_state(compare_id
, buf
, NULL
);
1591 ret
= state_to_comparison(state
);
1594 ret
= flip_comparison(ret
);
1599 int get_comparison(struct expression
*a
, struct expression
*b
)
1608 a
= strip_parens(a
);
1609 b
= strip_parens(b
);
1611 move_plus_to_minus(&a
, &b
);
1613 one
= chunk_to_var(a
);
1616 two
= chunk_to_var(b
);
1620 ret
= get_comparison_strings(one
, two
);
1624 if (is_plus_one(a
) || is_minus_one(a
)) {
1626 one
= chunk_to_var(a
->left
);
1627 ret
= get_comparison_strings(one
, two
);
1628 } else if (is_plus_one(b
) || is_minus_one(b
)) {
1630 two
= chunk_to_var(b
->left
);
1631 ret
= get_comparison_strings(one
, two
);
1637 if ((is_plus_one(a
) || is_minus_one(b
)) && ret
== '<')
1639 else if ((is_minus_one(a
) || is_plus_one(b
)) && ret
== '>')
1649 return comparison_from_extra(a
, b
);
1653 int possible_comparison(struct expression
*a
, int comparison
, struct expression
*b
)
1659 struct sm_state
*sm
;
1662 one
= chunk_to_var(a
);
1665 two
= chunk_to_var(b
);
1670 if (strcmp(one
, two
) == 0 && comparison
== SPECIAL_EQUAL
) {
1675 if (strcmp(one
, two
) > 0) {
1680 comparison
= flip_comparison(comparison
);
1683 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
1684 sm
= get_sm_state(compare_id
, buf
, NULL
);
1688 FOR_EACH_PTR(sm
->possible
, sm
) {
1689 if (!sm
->state
->data
)
1691 saved
= ((struct compare_data
*)sm
->state
->data
)->comparison
;
1692 if (saved
== comparison
)
1694 if (comparison
== SPECIAL_EQUAL
&&
1695 (saved
== SPECIAL_LTE
||
1696 saved
== SPECIAL_GTE
||
1697 saved
== SPECIAL_UNSIGNED_LTE
||
1698 saved
== SPECIAL_UNSIGNED_GTE
))
1702 } END_FOR_EACH_PTR(sm
);
1711 struct state_list
*get_all_comparisons(struct expression
*expr
)
1713 struct smatch_state
*state
;
1714 struct string_list
*links
;
1715 struct state_list
*ret
= NULL
;
1716 struct sm_state
*sm
;
1719 state
= get_state_chunk(link_id
, expr
);
1722 links
= state
->data
;
1724 FOR_EACH_PTR(links
, tmp
) {
1725 sm
= get_sm_state(compare_id
, tmp
, NULL
);
1728 // FIXME have to compare name with vsl
1729 add_ptr_list(&ret
, sm
);
1730 } END_FOR_EACH_PTR(tmp
);
1735 struct state_list
*get_all_possible_equal_comparisons(struct expression
*expr
)
1737 struct smatch_state
*state
;
1738 struct string_list
*links
;
1739 struct state_list
*ret
= NULL
;
1740 struct sm_state
*sm
;
1743 state
= get_state_chunk(link_id
, expr
);
1746 links
= state
->data
;
1748 FOR_EACH_PTR(links
, tmp
) {
1749 sm
= get_sm_state(compare_id
, tmp
, NULL
);
1752 if (!strchr(sm
->state
->name
, '='))
1754 if (strcmp(sm
->state
->name
, "!=") == 0)
1756 add_ptr_list(&ret
, sm
);
1757 } END_FOR_EACH_PTR(tmp
);
1762 struct state_list
*get_all_possible_not_equal_comparisons(struct expression
*expr
)
1764 struct smatch_state
*state
;
1765 struct string_list
*links
;
1766 struct state_list
*ret
= NULL
;
1767 struct sm_state
*sm
;
1768 struct sm_state
*possible
;
1773 state
= get_state_chunk(link_id
, expr
);
1776 links
= state
->data
;
1778 FOR_EACH_PTR(links
, link
) {
1779 sm
= get_sm_state(compare_id
, link
, NULL
);
1782 FOR_EACH_PTR(sm
->possible
, possible
) {
1783 if (strcmp(possible
->state
->name
, "!=") != 0)
1785 add_ptr_list(&ret
, sm
);
1787 } END_FOR_EACH_PTR(link
);
1788 } END_FOR_EACH_PTR(link
);
1793 static void update_links_from_call(struct expression
*left
,
1795 struct expression
*right
)
1797 struct string_list
*links
;
1798 struct smatch_state
*state
;
1799 struct compare_data
*data
;
1800 struct symbol
*left_sym
, *right_sym
;
1801 char *left_var
= NULL
;
1802 char *right_var
= NULL
;
1803 struct var_sym_list
*left_vsl
;
1804 struct expression
*expr
;
1806 struct var_sym_list
*vsl
;
1810 left_var
= chunk_to_var_sym(left
, &left_sym
);
1813 left_vsl
= expr_to_vsl(left
);
1814 right_var
= chunk_to_var_sym(right
, &right_sym
);
1818 state
= get_state(link_id
, right_var
, right_sym
);
1821 links
= state
->data
;
1823 FOR_EACH_PTR(links
, tmp
) {
1824 state
= get_state(compare_id
, tmp
, NULL
);
1825 if (!state
|| !state
->data
)
1828 comparison
= data
->comparison
;
1830 var
= data
->right_var
;
1831 vsl
= data
->right_vsl
;
1832 if (strcmp(var
, right_var
) == 0) {
1834 var
= data
->left_var
;
1835 vsl
= data
->left_vsl
;
1836 comparison
= flip_comparison(comparison
);
1838 comparison
= combine_comparisons(left_compare
, comparison
);
1841 add_comparison_var_sym(left
, left_var
, left_vsl
, comparison
, expr
, var
, vsl
);
1842 } END_FOR_EACH_PTR(tmp
);
1845 free_string(right_var
);
1848 void __add_return_comparison(struct expression
*call
, const char *range
)
1850 struct expression
*arg
;
1854 if (!str_to_comparison_arg(range
, call
, &comparison
, &arg
))
1856 snprintf(buf
, sizeof(buf
), "%s", show_special(comparison
));
1857 update_links_from_call(call
, comparison
, arg
);
1858 add_comparison(call
, comparison
, arg
);
1861 void __add_comparison_info(struct expression
*expr
, struct expression
*call
, const char *range
)
1863 copy_comparisons(expr
, call
);
1866 static char *get_mask_comparison(struct expression
*expr
, int ignore
)
1868 struct expression
*tmp
, *right
;
1872 /* The return value for "return foo & param;" is <= param */
1875 while ((tmp
= get_assigned_expr(expr
))) {
1876 expr
= strip_expr(tmp
);
1881 if (expr
->type
!= EXPR_BINOP
|| expr
->op
!= '&')
1884 right
= strip_expr(expr
->right
);
1885 param
= get_param_num(right
);
1887 if (param
== ignore
)
1890 snprintf(buf
, sizeof(buf
), "[<=$%d]", param
);
1891 return alloc_sname(buf
);
1894 static char *range_comparison_to_param_helper(struct expression
*expr
, char starts_with
, int ignore
)
1896 struct symbol
*param
;
1899 char *ret_str
= NULL
;
1906 var
= chunk_to_var(expr
);
1911 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
1917 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
1918 compare
= get_comparison_strings(var
, buf
);
1921 if (show_special(compare
)[0] != starts_with
)
1923 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_special(compare
), i
);
1924 ret_str
= alloc_sname(buf
);
1926 } END_FOR_EACH_PTR(param
);
1935 if (starts_with
== '<')
1936 ret_str
= get_mask_comparison(expr
, ignore
);
1940 char *name_sym_to_param_comparison(const char *name
, struct symbol
*sym
)
1942 struct symbol
*param
;
1948 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
1952 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
1953 compare
= get_comparison_strings(name
, buf
);
1956 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_special(compare
), i
);
1957 return alloc_sname(buf
);
1958 } END_FOR_EACH_PTR(param
);
1963 char *expr_equal_to_param(struct expression
*expr
, int ignore
)
1965 return range_comparison_to_param_helper(expr
, '=', ignore
);
1968 char *expr_lte_to_param(struct expression
*expr
, int ignore
)
1970 return range_comparison_to_param_helper(expr
, '<', ignore
);
1973 char *expr_param_comparison(struct expression
*expr
, int ignore
)
1975 struct symbol
*param
;
1978 char *ret_str
= NULL
;
1982 var
= chunk_to_var(expr
);
1987 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
1993 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
1994 compare
= get_comparison_strings(var
, buf
);
1997 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_special(compare
), i
);
1998 ret_str
= alloc_sname(buf
);
2000 } END_FOR_EACH_PTR(param
);
2007 char *get_printed_param_name(struct expression
*call
, const char *param_name
, struct symbol
*param_sym
)
2009 struct expression
*arg
;
2012 static char buf
[256];
2017 FOR_EACH_PTR(call
->args
, arg
) {
2020 name
= expr_to_var_sym(arg
, &sym
);
2023 if (sym
!= param_sym
)
2027 if (strncmp(name
, param_name
, len
) != 0)
2029 if (param_name
[len
] == '\0') {
2030 snprintf(buf
, sizeof(buf
), "$%d", i
);
2033 if (param_name
[len
] != '-')
2035 snprintf(buf
, sizeof(buf
), "$%d%s", i
, param_name
+ len
);
2037 } END_FOR_EACH_PTR(arg
);
2042 static void match_call_info(struct expression
*expr
)
2044 struct expression
*arg
;
2045 struct smatch_state
*state
;
2046 struct sm_state
*sm
;
2047 struct compare_data
*data
;
2049 struct string_list
*links
;
2051 const char *right_name
;
2057 FOR_EACH_PTR(expr
->args
, arg
) {
2060 state
= get_state_chunk(link_id
, arg
);
2064 links
= state
->data
;
2065 FOR_EACH_PTR(links
, link
) {
2066 struct var_sym_list
*right_vsl
;
2067 struct var_sym
*right_vs
;
2070 if (strstr(link
, " orig"))
2072 sm
= get_sm_state(compare_id
, link
, NULL
);
2075 data
= sm
->state
->data
;
2076 if (!data
|| !data
->comparison
)
2078 arg_name
= expr_to_var(arg
);
2083 if (strcmp(data
->left_var
, arg_name
) == 0) {
2084 comparison
= data
->comparison
;
2085 right_name
= data
->right_var
;
2086 right_vsl
= data
->right_vsl
;
2087 } else if (strcmp(data
->right_var
, arg_name
) == 0) {
2088 comparison
= flip_comparison(data
->comparison
);
2089 right_name
= data
->left_var
;
2090 right_vsl
= data
->left_vsl
;
2092 if (!right_vsl
|| ptr_list_size((struct ptr_list
*)right_vsl
) != 1)
2095 right_vs
= first_ptr_list((struct ptr_list
*)right_vsl
);
2096 if (strcmp(right_vs
->var
, right_name
) != 0)
2098 right_name
= get_printed_param_name(expr
, right_vs
->var
, right_vs
->sym
);
2101 snprintf(info_buf
, sizeof(info_buf
), "%s %s", show_special(comparison
), right_name
);
2102 sql_insert_caller_info(expr
, PARAM_COMPARE
, i
, "$", info_buf
);
2105 free_string(arg_name
);
2106 } END_FOR_EACH_PTR(link
);
2107 } END_FOR_EACH_PTR(arg
);
2110 static void struct_member_callback(struct expression
*call
, int param
, char *printed_name
, struct sm_state
*link_sm
)
2112 struct sm_state
*compare_sm
;
2113 struct string_list
*links
;
2115 struct compare_data
*data
;
2116 struct var_sym
*left
, *right
;
2117 static char info_buf
[256];
2118 const char *right_name
;
2120 if (strstr(printed_name
, " orig"))
2123 links
= link_sm
->state
->data
;
2124 FOR_EACH_PTR(links
, link
) {
2125 compare_sm
= get_sm_state(compare_id
, link
, NULL
);
2128 data
= compare_sm
->state
->data
;
2129 if (!data
|| !data
->comparison
)
2132 if (ptr_list_size((struct ptr_list
*)data
->left_vsl
) != 1 ||
2133 ptr_list_size((struct ptr_list
*)data
->right_vsl
) != 1)
2135 left
= first_ptr_list((struct ptr_list
*)data
->left_vsl
);
2136 right
= first_ptr_list((struct ptr_list
*)data
->right_vsl
);
2137 if (left
->sym
== right
->sym
&&
2138 strcmp(left
->var
, right
->var
) == 0)
2141 * Both parameters link to this comparison so only
2142 * record the first one.
2144 if (left
->sym
!= link_sm
->sym
||
2145 strcmp(left
->var
, link_sm
->name
) != 0)
2148 right_name
= get_printed_param_name(call
, right
->var
, right
->sym
);
2151 snprintf(info_buf
, sizeof(info_buf
), "%s %s", show_special(data
->comparison
), right_name
);
2152 sql_insert_caller_info(call
, PARAM_COMPARE
, param
, printed_name
, info_buf
);
2153 } END_FOR_EACH_PTR(link
);
2156 static void print_return_value_comparison(int return_id
, char *return_ranges
, struct expression
*expr
)
2159 const char *tmp_name
;
2165 * TODO: This only prints == comparisons. That's probably the most
2166 * useful comparison because == max has lots of implications. But it
2167 * would be good to capture the rest as well.
2169 * This information is already in the DB but it's in the parameter math
2170 * bits and it's awkward to use it. This is is the simpler, possibly
2171 * cleaner way, but not necessarily the best, I don't know.
2176 name
= expr_to_var_sym(expr
, &sym
);
2180 param
= get_param_num_from_sym(sym
);
2183 if (param_was_set_var_sym(name
, sym
))
2186 tmp_name
= get_param_name_var_sym(name
, sym
);
2190 snprintf(info_buf
, sizeof(info_buf
), "== $%d%s", param
, tmp_name
+ 1);
2191 sql_insert_return_states(return_id
, return_ranges
,
2192 PARAM_COMPARE
, -1, "$", info_buf
);
2197 static void print_return_comparison(int return_id
, char *return_ranges
, struct expression
*expr
)
2199 struct sm_state
*tmp
;
2200 struct string_list
*links
;
2202 struct sm_state
*sm
;
2203 struct compare_data
*data
;
2204 struct var_sym
*left
, *right
;
2205 int left_param
, right_param
;
2207 char right_buf
[256];
2209 const char *tmp_name
;
2211 print_return_value_comparison(return_id
, return_ranges
, expr
);
2213 FOR_EACH_MY_SM(link_id
, __get_cur_stree(), tmp
) {
2214 if (get_param_num_from_sym(tmp
->sym
) < 0)
2216 links
= tmp
->state
->data
;
2217 FOR_EACH_PTR(links
, link
) {
2218 sm
= get_sm_state(compare_id
, link
, NULL
);
2221 data
= sm
->state
->data
;
2222 if (!data
|| !data
->comparison
)
2224 if (ptr_list_size((struct ptr_list
*)data
->left_vsl
) != 1 ||
2225 ptr_list_size((struct ptr_list
*)data
->right_vsl
) != 1)
2227 left
= first_ptr_list((struct ptr_list
*)data
->left_vsl
);
2228 right
= first_ptr_list((struct ptr_list
*)data
->right_vsl
);
2229 if (left
->sym
== right
->sym
&&
2230 strcmp(left
->var
, right
->var
) == 0)
2233 * Both parameters link to this comparison so only
2234 * record the first one.
2236 if (left
->sym
!= tmp
->sym
||
2237 strcmp(left
->var
, tmp
->name
) != 0)
2240 if (strstr(right
->var
, " orig"))
2243 left_param
= get_param_num_from_sym(left
->sym
);
2244 right_param
= get_param_num_from_sym(right
->sym
);
2245 if (left_param
< 0 || right_param
< 0)
2248 tmp_name
= get_param_name_var_sym(left
->var
, left
->sym
);
2251 snprintf(left_buf
, sizeof(left_buf
), "%s", tmp_name
);
2253 tmp_name
= get_param_name_var_sym(right
->var
, right
->sym
);
2254 if (!tmp_name
|| tmp_name
[0] != '$')
2256 snprintf(right_buf
, sizeof(right_buf
), "$%d%s", right_param
, tmp_name
+ 1);
2259 * FIXME: this should reject $ type variables (as
2260 * opposed to $->foo type). Those should come from
2261 * smatch_param_compare_limit.c.
2264 snprintf(info_buf
, sizeof(info_buf
), "%s %s", show_special(data
->comparison
), right_buf
);
2265 sql_insert_return_states(return_id
, return_ranges
,
2266 PARAM_COMPARE
, left_param
, left_buf
, info_buf
);
2267 } END_FOR_EACH_PTR(link
);
2269 } END_FOR_EACH_SM(tmp
);
2272 static int parse_comparison(char **value
, int *op
)
2280 if (**value
== '=') {
2288 *op
= SPECIAL_EQUAL
;
2293 *op
= SPECIAL_NOTEQUAL
;
2297 if (**value
== '=') {
2306 if (**value
!= ' ') {
2307 sm_msg("internal error parsing comparison. %s", *value
);
2315 static int split_op_param_key(char *value
, int *op
, int *param
, char **key
)
2317 static char buf
[256];
2320 if (!parse_comparison(&value
, op
))
2323 snprintf(buf
, sizeof(buf
), value
);
2330 if (*param
< 0 || *param
> 99)
2342 static void db_return_comparison(struct expression
*expr
, int left_param
, char *key
, char *value
)
2344 struct expression
*left_arg
, *right_arg
;
2345 char *left_name
= NULL
;
2346 struct symbol
*left_sym
;
2347 char *right_name
= NULL
;
2348 struct symbol
*right_sym
;
2352 struct var_sym_list
*left_vsl
= NULL
, *right_vsl
= NULL
;
2354 if (left_param
== -1) {
2355 if (expr
->type
!= EXPR_ASSIGNMENT
)
2357 left_arg
= strip_expr(expr
->left
);
2359 while (expr
->type
== EXPR_ASSIGNMENT
)
2360 expr
= strip_expr(expr
->right
);
2361 if (expr
->type
!= EXPR_CALL
)
2364 while (expr
->type
== EXPR_ASSIGNMENT
)
2365 expr
= strip_expr(expr
->right
);
2366 if (expr
->type
!= EXPR_CALL
)
2369 left_arg
= get_argument_from_call_expr(expr
->args
, left_param
);
2374 if (!split_op_param_key(value
, &op
, &right_param
, &right_key
))
2377 right_arg
= get_argument_from_call_expr(expr
->args
, right_param
);
2381 left_name
= get_variable_from_key(left_arg
, key
, &left_sym
);
2382 if (!left_name
|| !left_sym
)
2385 right_name
= get_variable_from_key(right_arg
, right_key
, &right_sym
);
2386 if (!right_name
|| !right_sym
)
2389 add_var_sym(&left_vsl
, left_name
, left_sym
);
2390 add_var_sym(&right_vsl
, right_name
, right_sym
);
2392 add_comparison_var_sym(NULL
, left_name
, left_vsl
, op
, NULL
, right_name
, right_vsl
);
2395 free_string(left_name
);
2396 free_string(right_name
);
2399 int param_compare_limit_is_impossible(struct expression
*expr
, int left_param
, char *left_key
, char *value
)
2401 struct smatch_state
*state
;
2402 char *left_name
= NULL
;
2403 char *right_name
= NULL
;
2404 struct symbol
*left_sym
, *right_sym
;
2405 struct expression
*left_arg
, *right_arg
;
2412 while (expr
->type
== EXPR_ASSIGNMENT
)
2413 expr
= strip_expr(expr
->right
);
2414 if (expr
->type
!= EXPR_CALL
)
2417 if (!split_op_param_key(value
, &op
, &right_param
, &right_key
))
2420 left_arg
= get_argument_from_call_expr(expr
->args
, left_param
);
2424 right_arg
= get_argument_from_call_expr(expr
->args
, right_param
);
2428 left_name
= get_variable_from_key(left_arg
, left_key
, &left_sym
);
2429 right_name
= get_variable_from_key(right_arg
, right_key
, &right_sym
);
2430 if (!left_name
|| !right_name
)
2433 snprintf(buf
, sizeof(buf
), "%s vs %s", left_name
, right_name
);
2434 state
= get_state(compare_id
, buf
, NULL
);
2437 state_op
= state_to_comparison(state
);
2441 if (!filter_comparison(remove_unsigned_from_comparison(state_op
), op
))
2444 free_string(left_name
);
2445 free_string(right_name
);
2449 int impossibly_high_comparison(struct expression
*expr
)
2451 struct smatch_state
*link_state
;
2452 struct sm_state
*sm
;
2453 struct string_list
*links
;
2455 struct compare_data
*data
;
2457 link_state
= get_state_expr(link_id
, expr
);
2459 if (expr
->type
== EXPR_BINOP
&&
2460 (impossibly_high_comparison(expr
->left
) ||
2461 impossibly_high_comparison(expr
->right
)))
2466 links
= link_state
->data
;
2467 FOR_EACH_PTR(links
, link
) {
2468 sm
= get_sm_state(compare_id
, link
, NULL
);
2471 data
= sm
->state
->data
;
2474 if (!possibly_true(data
->left
, data
->comparison
, data
->right
))
2476 } END_FOR_EACH_PTR(link
);
2481 static void free_data(struct symbol
*sym
)
2485 clear_compare_data_alloc();
2488 void register_comparison(int id
)
2491 add_hook(&save_start_states
, AFTER_DEF_HOOK
);
2492 add_unmatched_state_hook(compare_id
, unmatched_comparison
);
2493 add_pre_merge_hook(compare_id
, &pre_merge_hook
);
2494 add_merge_hook(compare_id
, &merge_compare_states
);
2495 add_hook(&free_data
, AFTER_FUNC_HOOK
);
2496 add_hook(&match_call_info
, FUNCTION_CALL_HOOK
);
2497 add_split_return_callback(&print_return_comparison
);
2499 select_return_states_hook(PARAM_COMPARE
, &db_return_comparison
);
2500 add_hook(&match_preop
, OP_HOOK
);
2503 void register_comparison_late(int id
)
2505 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
2508 void register_comparison_links(int id
)
2511 add_merge_hook(link_id
, &merge_links
);
2512 add_modification_hook(link_id
, &match_modify
);
2513 add_modification_hook_late(link_id
, match_inc_dec
);
2515 add_member_info_callback(link_id
, struct_member_callback
);
2518 void register_comparison_inc_dec(int id
)
2521 add_modification_hook_late(inc_dec_id
, &iter_modify
);
2524 void register_comparison_inc_dec_links(int id
)
2526 inc_dec_link_id
= id
;
2527 set_up_link_functions(inc_dec_id
, inc_dec_link_id
);
2530 static void filter_by_sm(struct sm_state
*sm
, int op
,
2531 struct state_list
**true_stack
,
2532 struct state_list
**false_stack
)
2534 struct compare_data
*data
;
2540 data
= sm
->state
->data
;
2543 filter_by_sm(sm
->left
, op
, true_stack
, false_stack
);
2544 filter_by_sm(sm
->right
, op
, true_stack
, false_stack
);
2549 if (data
->comparison
&&
2550 data
->comparison
== filter_comparison(data
->comparison
, op
))
2553 if (data
->comparison
&&
2554 data
->comparison
== filter_comparison(data
->comparison
, negate_comparison(op
)))
2558 add_ptr_list(true_stack
, sm
);
2560 add_ptr_list(false_stack
, sm
);
2563 filter_by_sm(sm
->left
, op
, true_stack
, false_stack
);
2564 filter_by_sm(sm
->right
, op
, true_stack
, false_stack
);
2568 struct sm_state
*comparison_implication_hook(struct expression
*expr
,
2569 struct state_list
**true_stack
,
2570 struct state_list
**false_stack
)
2572 struct sm_state
*sm
;
2575 static char buf
[256];
2577 if (expr
->type
!= EXPR_COMPARE
)
2582 left
= expr_to_var(expr
->left
);
2583 right
= expr_to_var(expr
->right
);
2584 if (!left
|| !right
) {
2590 if (strcmp(left
, right
) > 0) {
2595 op
= flip_comparison(op
);
2598 snprintf(buf
, sizeof(buf
), "%s vs %s", left
, right
);
2599 sm
= get_sm_state(compare_id
, buf
, NULL
);
2605 filter_by_sm(sm
, op
, true_stack
, false_stack
);
2606 if (!*true_stack
&& !*false_stack
)
2610 sm_msg("implications from comparison: (%s)", show_sm(sm
));