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"
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 static const char *show_comparison(int comparison
)
62 if (comparison
== IMPOSSIBLE_COMPARISON
)
64 if (comparison
== UNKNOWN_COMPARISON
)
66 return show_special(comparison
);
69 struct smatch_state
*alloc_compare_state(
70 struct expression
*left
,
71 const char *left_var
, struct var_sym_list
*left_vsl
,
73 struct expression
*right
,
74 const char *right_var
, struct var_sym_list
*right_vsl
)
76 struct smatch_state
*state
;
77 struct compare_data
*data
;
79 state
= __alloc_smatch_state(0);
80 state
->name
= alloc_sname(show_comparison(comparison
));
81 data
= __alloc_compare_data(0);
83 data
->left_var
= alloc_sname(left_var
);
84 data
->left_vsl
= clone_var_sym_list(left_vsl
);
85 data
->comparison
= comparison
;
87 data
->right_var
= alloc_sname(right_var
);
88 data
->right_vsl
= clone_var_sym_list(right_vsl
);
93 int state_to_comparison(struct smatch_state
*state
)
95 if (!state
|| !state
->data
)
96 return UNKNOWN_COMPARISON
;
97 return ((struct compare_data
*)state
->data
)->comparison
;
101 * flip_comparison() reverses the op left and right. So "x >= y" becomes "y <= x".
103 int flip_comparison(int op
)
106 case UNKNOWN_COMPARISON
:
107 return UNKNOWN_COMPARISON
;
110 case SPECIAL_UNSIGNED_LT
:
111 return SPECIAL_UNSIGNED_GT
;
114 case SPECIAL_UNSIGNED_LTE
:
115 return SPECIAL_UNSIGNED_GTE
;
117 return SPECIAL_EQUAL
;
118 case SPECIAL_NOTEQUAL
:
119 return SPECIAL_NOTEQUAL
;
122 case SPECIAL_UNSIGNED_GTE
:
123 return SPECIAL_UNSIGNED_LTE
;
126 case SPECIAL_UNSIGNED_GT
:
127 return SPECIAL_UNSIGNED_LT
;
128 case IMPOSSIBLE_COMPARISON
:
129 return UNKNOWN_COMPARISON
;
131 sm_perror("unhandled comparison %d", op
);
136 int negate_comparison(int op
)
139 case UNKNOWN_COMPARISON
:
140 return UNKNOWN_COMPARISON
;
143 case SPECIAL_UNSIGNED_LT
:
144 return SPECIAL_UNSIGNED_GTE
;
147 case SPECIAL_UNSIGNED_LTE
:
148 return SPECIAL_UNSIGNED_GT
;
150 return SPECIAL_NOTEQUAL
;
151 case SPECIAL_NOTEQUAL
:
152 return SPECIAL_EQUAL
;
155 case SPECIAL_UNSIGNED_GTE
:
156 return SPECIAL_UNSIGNED_LT
;
159 case SPECIAL_UNSIGNED_GT
:
160 return SPECIAL_UNSIGNED_LTE
;
161 case IMPOSSIBLE_COMPARISON
:
162 return UNKNOWN_COMPARISON
;
164 sm_perror("unhandled comparison %d", op
);
169 static int rl_comparison(struct range_list
*left_rl
, struct range_list
*right_rl
)
171 sval_t left_min
, left_max
, right_min
, right_max
;
172 struct symbol
*type
= &int_ctype
;
174 if (!left_rl
|| !right_rl
)
175 return UNKNOWN_COMPARISON
;
177 if (type_positive_bits(rl_type(left_rl
)) > type_positive_bits(type
))
178 type
= rl_type(left_rl
);
179 if (type_positive_bits(rl_type(right_rl
)) > type_positive_bits(type
))
180 type
= rl_type(right_rl
);
182 left_rl
= cast_rl(type
, left_rl
);
183 right_rl
= cast_rl(type
, right_rl
);
185 left_min
= rl_min(left_rl
);
186 left_max
= rl_max(left_rl
);
187 right_min
= rl_min(right_rl
);
188 right_max
= rl_max(right_rl
);
190 if (left_min
.value
== left_max
.value
&&
191 right_min
.value
== right_max
.value
&&
192 left_min
.value
== right_min
.value
)
193 return SPECIAL_EQUAL
;
195 if (sval_cmp(left_max
, right_min
) < 0)
197 if (sval_cmp(left_max
, right_min
) == 0)
199 if (sval_cmp(left_min
, right_max
) > 0)
201 if (sval_cmp(left_min
, right_max
) == 0)
204 return UNKNOWN_COMPARISON
;
207 static int comparison_from_extra(struct expression
*a
, struct expression
*b
)
209 struct range_list
*left
, *right
;
211 if (!get_implied_rl(a
, &left
))
212 return UNKNOWN_COMPARISON
;
213 if (!get_implied_rl(b
, &right
))
214 return UNKNOWN_COMPARISON
;
216 return rl_comparison(left
, right
);
219 static struct range_list
*get_orig_rl(struct var_sym_list
*vsl
)
222 struct smatch_state
*state
;
226 sym
= vsl_to_sym(vsl
);
227 if (!sym
|| !sym
->ident
)
229 state
= get_orig_estate(sym
->ident
->name
, sym
);
230 return estate_rl(state
);
233 static struct smatch_state
*unmatched_comparison(struct sm_state
*sm
)
235 struct compare_data
*data
= sm
->state
->data
;
236 struct range_list
*left_rl
, *right_rl
;
237 int op
= UNKNOWN_COMPARISON
;
242 if (is_impossible_path()) {
243 op
= IMPOSSIBLE_COMPARISON
;
247 if (strstr(data
->left_var
, " orig"))
248 left_rl
= get_orig_rl(data
->left_vsl
);
249 else if (!get_implied_rl_var_sym(data
->left_var
, vsl_to_sym(data
->left_vsl
), &left_rl
))
252 if (strstr(data
->right_var
, " orig"))
253 right_rl
= get_orig_rl(data
->right_vsl
);
254 else if (!get_implied_rl_var_sym(data
->right_var
, vsl_to_sym(data
->right_vsl
), &right_rl
))
257 op
= rl_comparison(left_rl
, right_rl
);
260 return alloc_compare_state(data
->left
, data
->left_var
, data
->left_vsl
,
262 data
->right
, data
->right_var
, data
->right_vsl
);
265 /* remove_unsigned_from_comparison() is obviously a hack. */
266 int remove_unsigned_from_comparison(int op
)
269 case SPECIAL_UNSIGNED_LT
:
271 case SPECIAL_UNSIGNED_LTE
:
273 case SPECIAL_UNSIGNED_GTE
:
275 case SPECIAL_UNSIGNED_GT
:
283 * This is for when you merge states "a < b" and "a == b", the result is that
284 * we can say for sure, "a <= b" after the merge.
286 int merge_comparisons(int one
, int two
)
290 if (one
== UNKNOWN_COMPARISON
|| two
== UNKNOWN_COMPARISON
)
291 return UNKNOWN_COMPARISON
;
293 if (one
== IMPOSSIBLE_COMPARISON
)
295 if (two
== IMPOSSIBLE_COMPARISON
)
298 one
= remove_unsigned_from_comparison(one
);
299 two
= remove_unsigned_from_comparison(two
);
345 return UNKNOWN_COMPARISON
;
349 return SPECIAL_NOTEQUAL
;
356 return UNKNOWN_COMPARISON
;
360 * This is for if you have "a < b" and "b <= c" and you want to see how "a
361 * compares to c". You would call this like get_combined_comparison('<', '<=').
362 * The return comparison would be '<'.
364 int combine_comparisons(int left_compare
, int right_compare
)
368 left_compare
= remove_unsigned_from_comparison(left_compare
);
369 right_compare
= remove_unsigned_from_comparison(right_compare
);
373 switch (left_compare
) {
382 return right_compare
;
391 switch (right_compare
) {
420 return UNKNOWN_COMPARISON
;
424 * This is mostly used when you know from extra state that a <= b but you
425 * know from comparisons that a != b so then if take the intersection then
426 * we know that a < b. The name is taken from the fact that the intersection
429 int comparison_intersection(int left_compare
, int right_compare
)
431 int LT
, GT
, EQ
, NE
, total
;
433 if (left_compare
== IMPOSSIBLE_COMPARISON
||
434 right_compare
== IMPOSSIBLE_COMPARISON
)
435 return IMPOSSIBLE_COMPARISON
;
437 left_compare
= remove_unsigned_from_comparison(left_compare
);
438 right_compare
= remove_unsigned_from_comparison(right_compare
);
440 LT
= GT
= EQ
= NE
= total
= 0;
442 /* Only one side is known. */
444 return right_compare
;
448 switch (left_compare
) {
462 case SPECIAL_NOTEQUAL
:
476 return UNKNOWN_COMPARISON
;
479 switch (right_compare
) {
493 case SPECIAL_NOTEQUAL
:
507 return UNKNOWN_COMPARISON
;
522 return SPECIAL_EQUAL
;
523 if (total
== 2 && EQ
&& NE
)
524 return IMPOSSIBLE_COMPARISON
;
526 return IMPOSSIBLE_COMPARISON
;
532 return SPECIAL_NOTEQUAL
;
533 if (total
== 2 && (LT
|| GT
) && EQ
)
534 return IMPOSSIBLE_COMPARISON
;
536 return UNKNOWN_COMPARISON
;
539 static void pre_merge_hook(struct sm_state
*cur
, struct sm_state
*other
)
541 struct compare_data
*data
= cur
->state
->data
;
543 static bool in_recurse
;
545 // FIXME. No data is useless
552 extra
= comparison_from_extra(data
->left
, data
->right
);
556 new = comparison_intersection(extra
, data
->comparison
);
557 if (new == data
->comparison
)
560 // FIXME: we should always preserve implications
561 set_state(comparison_id
, cur
->name
, NULL
,
562 alloc_compare_state(data
->left
, data
->left_var
, data
->left_vsl
,
564 data
->right
, data
->right_var
, data
->right_vsl
));
567 struct smatch_state
*merge_compare_states(struct smatch_state
*s1
, struct smatch_state
*s2
)
569 struct compare_data
*data
= s1
->data
;
575 op
= merge_comparisons(state_to_comparison(s1
), state_to_comparison(s2
));
576 return alloc_compare_state(
577 data
->left
, data
->left_var
, data
->left_vsl
,
579 data
->right
, data
->right_var
, data
->right_vsl
);
582 static struct smatch_state
*alloc_link_state(struct string_list
*links
)
584 struct smatch_state
*state
;
585 static char buf
[256];
589 state
= __alloc_smatch_state(0);
592 FOR_EACH_PTR(links
, tmp
) {
594 snprintf(buf
, sizeof(buf
), "%s", tmp
);
596 append(buf
, ", ", sizeof(buf
));
597 append(buf
, tmp
, sizeof(buf
));
599 } END_FOR_EACH_PTR(tmp
);
601 state
->name
= alloc_sname(buf
);
606 static void save_start_states(struct statement
*stmt
)
608 struct symbol
*param
;
610 char state_name
[128];
611 struct smatch_state
*state
;
612 struct string_list
*links
;
615 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
616 struct var_sym_list
*left_vsl
= NULL
;
617 struct var_sym_list
*right_vsl
= NULL
;
621 snprintf(orig
, sizeof(orig
), "%s orig", param
->ident
->name
);
622 snprintf(state_name
, sizeof(state_name
), "%s vs %s", param
->ident
->name
, orig
);
623 add_var_sym(&left_vsl
, param
->ident
->name
, param
);
624 add_var_sym(&right_vsl
, orig
, param
);
625 state
= alloc_compare_state(
626 NULL
, param
->ident
->name
, left_vsl
,
628 NULL
, alloc_sname(orig
), right_vsl
);
629 set_state(comparison_id
, state_name
, NULL
, state
);
631 link
= alloc_sname(state_name
);
633 insert_string(&links
, link
);
634 state
= alloc_link_state(links
);
635 set_state(link_id
, param
->ident
->name
, param
, state
);
636 } END_FOR_EACH_PTR(param
);
639 static struct smatch_state
*merge_links(struct smatch_state
*s1
, struct smatch_state
*s2
)
641 struct smatch_state
*ret
;
642 struct string_list
*links
;
644 links
= combine_string_lists(s1
->data
, s2
->data
);
645 ret
= alloc_link_state(links
);
649 static void save_link_var_sym(const char *var
, struct symbol
*sym
, const char *link
)
651 struct smatch_state
*old_state
, *new_state
;
652 struct string_list
*links
;
655 old_state
= get_state(link_id
, var
, sym
);
657 links
= clone_str_list(old_state
->data
);
661 new = alloc_sname(link
);
662 insert_string(&links
, new);
664 new_state
= alloc_link_state(links
);
665 set_state(link_id
, var
, sym
, new_state
);
668 static void match_inc(struct sm_state
*sm
, bool preserve
)
670 struct string_list
*links
;
671 struct smatch_state
*state
, *new;
672 struct compare_data
*data
;
677 links
= sm
->state
->data
;
679 FOR_EACH_PTR(links
, tmp
) {
680 state
= get_state(comparison_id
, tmp
, NULL
);
688 if (strncmp(sm
->name
, tmp
, strlen(sm
->name
)) != 0 ||
689 tmp
[strlen(sm
->name
)] != ' ')
692 op
= state_to_comparison(state
);
694 switch (flip
? flip_comparison(op
) : op
) {
697 case SPECIAL_UNSIGNED_GTE
:
699 case SPECIAL_UNSIGNED_GT
:
702 new = alloc_compare_state(
703 data
->left
, data
->left_var
, data
->left_vsl
,
705 data
->right
, data
->right_var
, data
->right_vsl
);
706 set_state(comparison_id
, tmp
, NULL
, new);
709 case SPECIAL_UNSIGNED_LT
:
710 new = alloc_compare_state(
711 data
->left
, data
->left_var
, data
->left_vsl
,
712 flip
? SPECIAL_GTE
: SPECIAL_LTE
,
713 data
->right
, data
->right_var
, data
->right_vsl
);
714 set_state(comparison_id
, tmp
, NULL
, new);
717 new = alloc_compare_state(
718 data
->left
, data
->left_var
, data
->left_vsl
,
720 data
->right
, data
->right_var
, data
->right_vsl
);
721 set_state(comparison_id
, tmp
, NULL
, new);
723 } END_FOR_EACH_PTR(tmp
);
726 static void match_dec(struct sm_state
*sm
, bool preserve
)
728 struct string_list
*links
;
729 struct smatch_state
*state
;
732 links
= sm
->state
->data
;
734 FOR_EACH_PTR(links
, tmp
) {
735 struct compare_data
*data
;
736 struct smatch_state
*new;
738 state
= get_state(comparison_id
, tmp
, NULL
);
739 if (!state
|| !state
->data
)
744 switch (state_to_comparison(state
)) {
747 case SPECIAL_UNSIGNED_LTE
:
749 case SPECIAL_UNSIGNED_LT
: {
753 new = alloc_compare_state(
754 data
->left
, data
->left_var
, data
->left_vsl
,
756 data
->right
, data
->right_var
, data
->right_vsl
);
757 set_state(comparison_id
, tmp
, NULL
, new);
761 new = alloc_compare_state(
762 data
->left
, data
->left_var
, data
->left_vsl
,
764 data
->right
, data
->right_var
, data
->right_vsl
);
765 set_state(comparison_id
, tmp
, NULL
, new);
767 } END_FOR_EACH_PTR(tmp
);
770 static void reset_sm(struct sm_state
*sm
)
772 struct string_list
*links
;
775 links
= sm
->state
->data
;
777 FOR_EACH_PTR(links
, tmp
) {
778 struct smatch_state
*old
, *new;
780 old
= get_state(comparison_id
, tmp
, NULL
);
781 if (!old
|| !old
->data
) {
784 struct compare_data
*data
= old
->data
;
786 new = alloc_compare_state(
787 data
->left
, data
->left_var
, data
->left_vsl
,
789 data
->right
, data
->right_var
, data
->right_vsl
);
791 set_state(comparison_id
, tmp
, NULL
, new);
792 } END_FOR_EACH_PTR(tmp
);
793 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
796 static bool match_add_sub_assign(struct sm_state
*sm
, struct expression
*expr
)
798 struct range_list
*rl
;
799 sval_t zero
= { .type
= &int_ctype
};
801 if (!expr
|| expr
->type
!= EXPR_ASSIGNMENT
)
803 if (expr
->op
!= SPECIAL_ADD_ASSIGN
&& expr
->op
!= SPECIAL_SUB_ASSIGN
)
806 get_absolute_rl(expr
->right
, &rl
);
807 if (sval_is_negative(rl_min(rl
))) {
812 if (expr
->op
== SPECIAL_ADD_ASSIGN
)
813 match_inc(sm
, rl_has_sval(rl
, zero
));
815 match_dec(sm
, rl_has_sval(rl
, zero
));
819 static void match_inc_dec(struct sm_state
*sm
, struct expression
*mod_expr
)
822 * if (foo > bar) then ++foo is also > bar.
826 if (match_add_sub_assign(sm
, mod_expr
))
828 if (mod_expr
->type
!= EXPR_PREOP
&& mod_expr
->type
!= EXPR_POSTOP
)
831 if (mod_expr
->op
== SPECIAL_INCREMENT
)
832 match_inc(sm
, false);
833 else if (mod_expr
->op
== SPECIAL_DECREMENT
)
834 match_dec(sm
, false);
837 static int is_self_assign(struct expression
*expr
)
839 if (!expr
|| expr
->type
!= EXPR_ASSIGNMENT
|| expr
->op
!= '=')
841 return expr_equiv(expr
->left
, expr
->right
);
844 static void match_modify(struct sm_state
*sm
, struct expression
*mod_expr
)
846 if (mod_expr
&& is_self_assign(mod_expr
))
849 /* handled by match_inc_dec() */
851 ((mod_expr
->type
== EXPR_PREOP
|| mod_expr
->type
== EXPR_POSTOP
) &&
852 (mod_expr
->op
== SPECIAL_INCREMENT
|| mod_expr
->op
== SPECIAL_DECREMENT
)))
854 if (mod_expr
&& mod_expr
->type
== EXPR_ASSIGNMENT
&&
855 (mod_expr
->op
== SPECIAL_ADD_ASSIGN
|| mod_expr
->op
== SPECIAL_SUB_ASSIGN
))
861 static void match_preop(struct expression
*expr
)
863 struct expression
*parent
;
864 struct range_list
*left
, *right
;
868 * This is an important special case. Say you have:
872 * Assume that we know the range of limit is higher than the start
873 * value for "j". Then the first thing that we process is the ++j. We
874 * have not comparison states set up so it doesn't get caught by the
875 * modification hook. But it does get caught by smatch_extra which sets
876 * j to unknown then we parse the "j == limit" and sets false to != but
877 * really we want false to be <.
879 * So what we do is we set j < limit here, then the match_modify catches
880 * it and we do a match_inc_dec().
884 if (expr
->type
!= EXPR_PREOP
||
885 (expr
->op
!= SPECIAL_INCREMENT
&& expr
->op
!= SPECIAL_DECREMENT
))
888 parent
= expr_get_parent_expr(expr
);
891 if (parent
->type
!= EXPR_COMPARE
|| parent
->op
!= SPECIAL_EQUAL
)
893 if (parent
->left
!= expr
)
896 if (!get_implied_rl(expr
->unop
, &left
) ||
897 !get_implied_rl(parent
->right
, &right
))
900 op
= rl_comparison(left
, right
);
901 if (op
== UNKNOWN_COMPARISON
)
904 add_comparison(expr
->unop
, op
, parent
->right
);
907 static char *chunk_to_var_sym(struct expression
*expr
, struct symbol
**sym
)
909 expr
= strip_expr(expr
);
915 if (expr
->type
== EXPR_PREOP
&&
916 (expr
->op
== SPECIAL_INCREMENT
||
917 expr
->op
== SPECIAL_DECREMENT
))
918 expr
= strip_expr(expr
->unop
);
920 if (expr
->type
== EXPR_CALL
) {
923 snprintf(buf
, sizeof(buf
), "return %p", expr
);
924 return alloc_string(buf
);
927 return expr_to_chunk_sym_vsl(expr
, sym
, NULL
);
930 static char *chunk_to_var(struct expression
*expr
)
932 return chunk_to_var_sym(expr
, NULL
);
935 static struct smatch_state
*get_state_chunk(int owner
, struct expression
*expr
)
939 struct smatch_state
*ret
;
941 name
= chunk_to_var_sym(expr
, &sym
);
945 ret
= get_state(owner
, name
, sym
);
950 static void save_link(struct expression
*expr
, char *link
)
955 expr
= strip_expr(expr
);
956 if (expr
->type
== EXPR_BINOP
) {
959 chunk
= chunk_to_var(expr
);
963 save_link(expr
->left
, link
);
964 save_link(expr
->right
, link
);
965 save_link_var_sym(chunk
, NULL
, link
);
969 var
= chunk_to_var_sym(expr
, &sym
);
973 save_link_var_sym(var
, sym
, link
);
977 static int get_orig_comparison(struct stree
*pre_stree
, const char *left
, const char *right
)
979 struct smatch_state
*state
;
980 struct compare_data
*data
;
982 char state_name
[256];
984 if (strcmp(left
, right
) > 0) {
985 const char *tmp
= right
;
992 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
993 state
= get_state_stree(pre_stree
, comparison_id
, state_name
, NULL
);
994 if (!state
|| !state
->data
)
998 return flip_comparison(data
->comparison
);
999 return data
->comparison
;
1003 static int have_common_var_sym(struct var_sym_list
*left_vsl
, struct var_sym_list
*right_vsl
)
1005 struct var_sym
*tmp
;
1007 FOR_EACH_PTR(left_vsl
, tmp
) {
1008 if (in_var_sym_list(right_vsl
, tmp
->var
, tmp
->sym
))
1010 } END_FOR_EACH_PTR(tmp
);
1016 * The idea here is that we take a comparison "a < b" and then we look at all
1017 * the things which "b" is compared against "b < c" and we say that that implies
1018 * a relationship "a < c".
1020 * The names here about because the comparisons are organized like this
1024 static void update_tf_links(struct stree
*pre_stree
,
1025 struct expression
*left_expr
,
1026 const char *left_var
, struct var_sym_list
*left_vsl
,
1027 int left_comparison
, int left_false_comparison
,
1028 const char *mid_var
, struct var_sym_list
*mid_vsl
,
1029 struct string_list
*links
)
1031 struct smatch_state
*state
;
1032 struct smatch_state
*true_state
, *false_state
;
1033 struct compare_data
*data
;
1034 struct expression
*right_expr
;
1035 const char *right_var
;
1036 struct var_sym_list
*right_vsl
;
1037 int orig_comparison
;
1038 int right_comparison
;
1039 int true_comparison
;
1040 int false_comparison
;
1042 char state_name
[256];
1045 FOR_EACH_PTR(links
, tmp
) {
1046 state
= get_state_stree(pre_stree
, comparison_id
, tmp
, NULL
);
1047 if (!state
|| !state
->data
)
1050 right_comparison
= data
->comparison
;
1051 right_expr
= data
->right
;
1052 right_var
= data
->right_var
;
1053 right_vsl
= data
->right_vsl
;
1054 if (strcmp(mid_var
, right_var
) == 0) {
1055 right_expr
= data
->left
;
1056 right_var
= data
->left_var
;
1057 right_vsl
= data
->left_vsl
;
1058 right_comparison
= flip_comparison(right_comparison
);
1060 if (have_common_var_sym(left_vsl
, right_vsl
))
1063 orig_comparison
= get_orig_comparison(pre_stree
, left_var
, right_var
);
1065 true_comparison
= combine_comparisons(left_comparison
, right_comparison
);
1066 false_comparison
= combine_comparisons(left_false_comparison
, right_comparison
);
1068 true_comparison
= comparison_intersection(orig_comparison
, true_comparison
);
1069 false_comparison
= comparison_intersection(orig_comparison
, false_comparison
);
1071 if (strcmp(left_var
, right_var
) > 0) {
1072 struct expression
*tmp_expr
= left_expr
;
1073 const char *tmp_var
= left_var
;
1074 struct var_sym_list
*tmp_vsl
= left_vsl
;
1076 left_expr
= right_expr
;
1077 left_var
= right_var
;
1078 left_vsl
= right_vsl
;
1079 right_expr
= tmp_expr
;
1080 right_var
= tmp_var
;
1081 right_vsl
= tmp_vsl
;
1082 true_comparison
= flip_comparison(true_comparison
);
1083 false_comparison
= flip_comparison(false_comparison
);
1086 if (!true_comparison
&& !false_comparison
)
1089 if (true_comparison
)
1090 true_state
= alloc_compare_state(
1091 left_expr
, left_var
, left_vsl
,
1093 right_expr
, right_var
, right_vsl
);
1096 if (false_comparison
)
1097 false_state
= alloc_compare_state(
1098 left_expr
, left_var
, left_vsl
,
1100 right_expr
, right_var
, right_vsl
);
1104 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_var
, right_var
);
1105 set_true_false_states(comparison_id
, state_name
, NULL
, true_state
, false_state
);
1106 FOR_EACH_PTR(left_vsl
, vs
) {
1107 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
1108 } END_FOR_EACH_PTR(vs
);
1109 FOR_EACH_PTR(right_vsl
, vs
) {
1110 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
1111 } END_FOR_EACH_PTR(vs
);
1112 if (!vsl_to_sym(left_vsl
))
1113 save_link_var_sym(left_var
, NULL
, state_name
);
1114 if (!vsl_to_sym(right_vsl
))
1115 save_link_var_sym(right_var
, NULL
, state_name
);
1116 } END_FOR_EACH_PTR(tmp
);
1119 static void update_tf_data(struct stree
*pre_stree
,
1120 struct expression
*left_expr
,
1121 const char *left_name
, struct var_sym_list
*left_vsl
,
1122 struct expression
*right_expr
,
1123 const char *right_name
, struct var_sym_list
*right_vsl
,
1124 int true_comparison
, int false_comparison
)
1126 struct smatch_state
*state
;
1128 state
= get_state_stree(pre_stree
, link_id
, right_name
, vsl_to_sym(right_vsl
));
1130 update_tf_links(pre_stree
, left_expr
, left_name
, left_vsl
, true_comparison
, false_comparison
, right_name
, right_vsl
, state
->data
);
1132 state
= get_state_stree(pre_stree
, link_id
, left_name
, vsl_to_sym(left_vsl
));
1134 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
);
1137 static void iter_modify(struct sm_state
*sm
, struct expression
*mod_expr
)
1139 if (sm
->state
!= &start
||
1141 (mod_expr
->type
!= EXPR_PREOP
&& mod_expr
->type
!= EXPR_POSTOP
) ||
1142 mod_expr
->op
!= SPECIAL_INCREMENT
)
1143 set_state(inc_dec_id
, sm
->name
, sm
->sym
, &undefined
);
1145 set_state(inc_dec_id
, sm
->name
, sm
->sym
, &incremented
);
1148 static void handle_for_loops(struct expression
*expr
, char *state_name
, struct smatch_state
*false_state
)
1151 char *iter_name
, *cap_name
;
1152 struct symbol
*iter_sym
, *cap_sym
;
1153 struct compare_data
*data
;
1155 if (expr
->op
!= '<' && expr
->op
!= SPECIAL_UNSIGNED_LT
)
1158 if (!__cur_stmt
|| !__prev_stmt
)
1160 if (__cur_stmt
->type
!= STMT_ITERATOR
)
1162 if (__cur_stmt
->iterator_pre_condition
!= expr
)
1165 /* literals are handled in smatch_extra.c */
1166 if (get_value(expr
->right
, &sval
))
1169 /* First time checking the condition */
1170 if (__prev_stmt
== __cur_stmt
->iterator_pre_statement
) {
1171 if (!get_implied_value(expr
->left
, &sval
) ||
1175 iter_name
= expr_to_var_sym(expr
->left
, &iter_sym
);
1176 cap_name
= expr_to_var_sym(expr
->right
, &cap_sym
);
1177 if (!iter_name
|| !cap_name
|| !iter_sym
|| !cap_sym
) {
1178 free_string(iter_name
);
1179 free_string(cap_name
);
1183 set_state(inc_dec_id
, iter_name
, iter_sym
, &start
);
1184 store_link(inc_dec_link_id
, cap_name
, cap_sym
, iter_name
, iter_sym
);
1186 free_string(iter_name
);
1187 free_string(cap_name
);
1191 /* Second time checking the condtion */
1192 if (__prev_stmt
!= __cur_stmt
->iterator_post_statement
)
1195 if (get_state_chunk(inc_dec_id
, expr
->left
) != &incremented
)
1198 data
= false_state
->data
;
1199 false_state
= alloc_compare_state(
1200 data
->left
, data
->left_var
, data
->left_vsl
,
1202 data
->right
, data
->right_var
, data
->right_vsl
);
1204 // FIXME: This doesn't handle links correct so it doesn't set "param orig"
1205 set_true_false_states(comparison_id
, state_name
, NULL
, NULL
, false_state
);
1208 static int is_plus_one(struct expression
*expr
)
1212 if (expr
->type
!= EXPR_BINOP
|| expr
->op
!= '+')
1214 if (!get_implied_value(expr
->right
, &sval
) || sval
.value
!= 1)
1219 static int is_minus_one(struct expression
*expr
)
1223 if (expr
->type
!= EXPR_BINOP
|| expr
->op
!= '-')
1225 if (!get_implied_value(expr
->right
, &sval
) || sval
.value
!= 1)
1230 static void remove_plus_minus_zero(struct expression
**expr_p
)
1232 struct expression
*expr
= *expr_p
;
1235 if (!expr
|| expr
->type
!= EXPR_BINOP
)
1237 if (expr
->op
== '+') {
1238 if (get_implied_value(expr
->left
, &sval
) && sval
.value
== 0)
1239 *expr_p
= expr
->right
;
1240 else if (get_implied_value(expr
->right
, &sval
) && sval
.value
== 0)
1241 *expr_p
= expr
->left
;
1244 return remove_plus_minus_zero(expr_p
);
1246 if (expr
->op
== '-') {
1247 if (get_implied_value(expr
->right
, &sval
) && sval
.value
== 0) {
1248 *expr_p
= expr
->left
;
1249 return remove_plus_minus_zero(expr_p
);
1254 static void move_plus_to_minus_helper(struct expression
**left_p
, struct expression
**right_p
)
1256 struct expression
*left
= *left_p
;
1257 struct expression
*right
= *right_p
;
1260 * These two are basically equivalent: "foo + 1 != bar" and
1261 * "foo != bar - 1". There are issues with signedness and integer
1262 * overflows. There are also issues with type as well. But let's
1263 * pretend we can ignore all that stuff for now.
1267 if (!is_plus_one(left
))
1270 *left_p
= left
->left
;
1271 *right_p
= binop_expression(right
, '-', left
->right
);
1274 static void move_plus_to_minus(struct expression
**left_p
, struct expression
**right_p
)
1276 if (is_plus_one(*left_p
) && is_plus_one(*right_p
))
1279 move_plus_to_minus_helper(left_p
, right_p
);
1280 move_plus_to_minus_helper(right_p
, left_p
);
1283 static void simplify_binops(struct expression
**left_p
, struct expression
**right_p
)
1285 remove_plus_minus_zero(left_p
);
1286 remove_plus_minus_zero(right_p
);
1288 move_plus_to_minus(left_p
, right_p
);
1291 static void handle_comparison(struct expression
*left_expr
, int op
, struct expression
*right_expr
, char **_state_name
, struct smatch_state
**_false_state
)
1295 struct symbol
*left_sym
, *right_sym
;
1296 struct var_sym_list
*left_vsl
= NULL
;
1297 struct var_sym_list
*right_vsl
= NULL
;
1299 int orig_comparison
;
1300 struct smatch_state
*true_state
, *false_state
;
1301 static char state_name
[256];
1302 struct stree
*pre_stree
;
1305 if (!left_expr
|| !right_expr
)
1308 left_expr
= strip_parens(left_expr
);
1309 right_expr
= strip_parens(right_expr
);
1311 while (left_expr
->type
== EXPR_ASSIGNMENT
)
1312 left_expr
= strip_parens(left_expr
->left
);
1313 while (right_expr
->type
== EXPR_ASSIGNMENT
)
1314 right_expr
= strip_parens(right_expr
->left
);
1316 false_op
= negate_comparison(op
);
1318 simplify_binops(&left_expr
, &right_expr
);
1320 if (op
== SPECIAL_UNSIGNED_LT
&&
1321 get_implied_value(left_expr
, &sval
) &&
1323 false_op
= SPECIAL_EQUAL
;
1325 if (op
== SPECIAL_UNSIGNED_GT
&&
1326 get_implied_value(right_expr
, &sval
) &&
1328 false_op
= SPECIAL_EQUAL
;
1330 left
= chunk_to_var_sym(left_expr
, &left_sym
);
1334 add_var_sym(&left_vsl
, left
, left_sym
);
1336 left_vsl
= expr_to_vsl(left_expr
);
1337 right
= chunk_to_var_sym(right_expr
, &right_sym
);
1341 add_var_sym(&right_vsl
, right
, right_sym
);
1343 right_vsl
= expr_to_vsl(right_expr
);
1345 if (strcmp(left
, right
) > 0) {
1346 char *tmp_name
= left
;
1347 struct var_sym_list
*tmp_vsl
= left_vsl
;
1348 struct expression
*tmp_expr
= left_expr
;
1351 left_vsl
= right_vsl
;
1352 left_expr
= right_expr
;
1354 right_vsl
= tmp_vsl
;
1355 right_expr
= tmp_expr
;
1356 op
= flip_comparison(op
);
1357 false_op
= flip_comparison(false_op
);
1360 orig_comparison
= get_comparison(left_expr
, right_expr
);
1361 op
= comparison_intersection(orig_comparison
, op
);
1362 false_op
= comparison_intersection(orig_comparison
, false_op
);
1364 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
1365 true_state
= alloc_compare_state(
1366 left_expr
, left
, left_vsl
,
1368 right_expr
, right
, right_vsl
);
1369 false_state
= alloc_compare_state(
1370 left_expr
, left
, left_vsl
,
1372 right_expr
, right
, right_vsl
);
1374 pre_stree
= clone_stree(__get_cur_stree());
1375 update_tf_data(pre_stree
, left_expr
, left
, left_vsl
, right_expr
, right
, right_vsl
, op
, false_op
);
1376 free_stree(&pre_stree
);
1378 set_true_false_states(comparison_id
, state_name
, NULL
, true_state
, false_state
);
1379 __compare_param_limit_hook(left_expr
, right_expr
, state_name
, true_state
, false_state
);
1380 save_link(left_expr
, state_name
);
1381 save_link(right_expr
, state_name
);
1384 *_false_state
= false_state
;
1386 *_state_name
= state_name
;
1392 void __comparison_match_condition(struct expression
*expr
)
1394 struct expression
*left
, *right
, *new_left
, *new_right
, *tmp
;
1395 struct smatch_state
*false_state
= NULL
;
1396 char *state_name
= NULL
;
1399 if (expr
->type
!= EXPR_COMPARE
)
1402 handle_comparison(expr
->left
, expr
->op
, expr
->right
, &state_name
, &false_state
);
1403 if (false_state
&& state_name
)
1404 handle_for_loops(expr
, state_name
, false_state
);
1406 left
= strip_parens(expr
->left
);
1407 right
= strip_parens(expr
->right
);
1409 if (left
->type
== EXPR_BINOP
&& left
->op
== '+') {
1410 new_left
= left
->left
;
1411 new_right
= binop_expression(right
, '-', left
->right
);
1412 handle_comparison(new_left
, expr
->op
, new_right
, NULL
, NULL
);
1414 new_left
= left
->right
;
1415 new_right
= binop_expression(right
, '-', left
->left
);
1416 handle_comparison(new_left
, expr
->op
, new_right
, NULL
, NULL
);
1420 left
= strip_parens(expr
->left
);
1421 right
= strip_parens(expr
->right
);
1422 if (get_last_expr_from_expression_stmt(expr
->left
)) {
1423 left
= get_last_expr_from_expression_stmt(expr
->left
);
1426 if (get_last_expr_from_expression_stmt(expr
->right
)) {
1427 right
= get_last_expr_from_expression_stmt(expr
->right
);
1435 while ((tmp
= get_assigned_expr(left
))) {
1438 left
= strip_expr(tmp
);
1441 while ((tmp
= get_assigned_expr(right
))) {
1444 right
= strip_expr(tmp
);
1447 handle_comparison(left
, expr
->op
, right
, NULL
, NULL
);
1450 static void add_comparison_var_sym(
1451 struct expression
*left_expr
,
1452 const char *left_name
, struct var_sym_list
*left_vsl
,
1454 struct expression
*right_expr
,
1455 const char *right_name
, struct var_sym_list
*right_vsl
)
1457 struct smatch_state
*state
;
1459 char state_name
[256];
1461 if (strcmp(left_name
, right_name
) > 0) {
1462 struct expression
*tmp_expr
= left_expr
;
1463 const char *tmp_name
= left_name
;
1464 struct var_sym_list
*tmp_vsl
= left_vsl
;
1466 left_expr
= right_expr
;
1467 left_name
= right_name
;
1468 left_vsl
= right_vsl
;
1469 right_expr
= tmp_expr
;
1470 right_name
= tmp_name
;
1471 right_vsl
= tmp_vsl
;
1472 comparison
= flip_comparison(comparison
);
1474 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_name
, right_name
);
1475 state
= alloc_compare_state(
1476 left_expr
, left_name
, left_vsl
,
1478 right_expr
, right_name
, right_vsl
);
1480 set_state(comparison_id
, state_name
, NULL
, state
);
1482 FOR_EACH_PTR(left_vsl
, vs
) {
1483 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
1484 } END_FOR_EACH_PTR(vs
);
1485 FOR_EACH_PTR(right_vsl
, vs
) {
1486 save_link_var_sym(vs
->var
, vs
->sym
, state_name
);
1487 } END_FOR_EACH_PTR(vs
);
1490 static void add_comparison(struct expression
*left
, int comparison
, struct expression
*right
)
1492 char *left_name
= NULL
;
1493 char *right_name
= NULL
;
1494 struct symbol
*left_sym
, *right_sym
;
1495 struct var_sym_list
*left_vsl
, *right_vsl
;
1496 struct smatch_state
*state
;
1497 char state_name
[256];
1499 left_name
= chunk_to_var_sym(left
, &left_sym
);
1502 left_vsl
= expr_to_vsl(left
);
1503 right_name
= chunk_to_var_sym(right
, &right_sym
);
1506 right_vsl
= expr_to_vsl(right
);
1508 if (strcmp(left_name
, right_name
) > 0) {
1509 struct expression
*tmp_expr
= left
;
1510 struct symbol
*tmp_sym
= left_sym
;
1511 char *tmp_name
= left_name
;
1512 struct var_sym_list
*tmp_vsl
= left_vsl
;
1515 left_name
= right_name
;
1516 left_sym
= right_sym
;
1517 left_vsl
= right_vsl
;
1519 right_name
= tmp_name
;
1520 right_sym
= tmp_sym
;
1521 right_vsl
= tmp_vsl
;
1522 comparison
= flip_comparison(comparison
);
1524 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_name
, right_name
);
1525 state
= alloc_compare_state(
1526 left
, left_name
, left_vsl
,
1528 right
, right_name
, right_vsl
);
1530 set_state(comparison_id
, state_name
, NULL
, state
);
1531 save_link(left
, state_name
);
1532 save_link(right
, state_name
);
1535 free_string(left_name
);
1536 free_string(right_name
);
1539 static void match_assign_add(struct expression
*expr
)
1541 struct expression
*right
;
1542 struct expression
*r_left
, *r_right
;
1543 sval_t left_tmp
, right_tmp
;
1545 right
= strip_expr(expr
->right
);
1546 r_left
= strip_expr(right
->left
);
1547 r_right
= strip_expr(right
->right
);
1549 get_absolute_min(r_left
, &left_tmp
);
1550 get_absolute_min(r_right
, &right_tmp
);
1552 if (left_tmp
.value
> 0)
1553 add_comparison(expr
->left
, '>', r_right
);
1554 else if (left_tmp
.value
== 0)
1555 add_comparison(expr
->left
, SPECIAL_GTE
, r_right
);
1557 if (right_tmp
.value
> 0)
1558 add_comparison(expr
->left
, '>', r_left
);
1559 else if (right_tmp
.value
== 0)
1560 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
1563 static void match_assign_sub(struct expression
*expr
)
1565 struct expression
*right
;
1566 struct expression
*r_left
, *r_right
;
1570 right
= strip_expr(expr
->right
);
1571 r_left
= strip_expr(right
->left
);
1572 r_right
= strip_expr(right
->right
);
1574 if (get_absolute_min(r_right
, &min
) && sval_is_negative(min
))
1577 comparison
= get_comparison(r_left
, r_right
);
1579 switch (comparison
) {
1582 if (implied_not_equal(r_right
, 0))
1583 add_comparison(expr
->left
, '>', r_left
);
1585 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
1590 static void match_assign_divide(struct expression
*expr
)
1592 struct expression
*right
;
1593 struct expression
*r_left
, *r_right
;
1596 right
= strip_expr(expr
->right
);
1597 r_left
= strip_expr(right
->left
);
1598 r_right
= strip_expr(right
->right
);
1599 if (!get_implied_min(r_right
, &min
) || min
.value
<= 1)
1602 add_comparison(expr
->left
, '<', r_left
);
1605 static void match_binop_assign(struct expression
*expr
)
1607 struct expression
*right
;
1609 right
= strip_expr(expr
->right
);
1610 if (right
->op
== '+')
1611 match_assign_add(expr
);
1612 if (right
->op
== '-')
1613 match_assign_sub(expr
);
1614 if (right
->op
== '/')
1615 match_assign_divide(expr
);
1618 static void copy_comparisons(struct expression
*left
, struct expression
*right
)
1620 struct string_list
*links
;
1621 struct smatch_state
*state
;
1622 struct compare_data
*data
;
1623 struct symbol
*left_sym
, *right_sym
;
1624 char *left_var
= NULL
;
1625 char *right_var
= NULL
;
1626 struct var_sym_list
*left_vsl
;
1627 struct expression
*expr
;
1629 struct var_sym_list
*vsl
;
1633 left_var
= chunk_to_var_sym(left
, &left_sym
);
1636 left_vsl
= expr_to_vsl(left
);
1637 right_var
= chunk_to_var_sym(right
, &right_sym
);
1641 state
= get_state(link_id
, right_var
, right_sym
);
1644 links
= state
->data
;
1646 FOR_EACH_PTR(links
, tmp
) {
1647 state
= get_state(comparison_id
, tmp
, NULL
);
1648 if (!state
|| !state
->data
)
1651 comparison
= data
->comparison
;
1653 var
= data
->right_var
;
1654 vsl
= data
->right_vsl
;
1655 if (strcmp(var
, right_var
) == 0) {
1657 var
= data
->left_var
;
1658 vsl
= data
->left_vsl
;
1659 comparison
= flip_comparison(comparison
);
1661 /* n = copy_from_user(dest, src, n); leads to n <= n which is nonsense */
1662 if (strcmp(left_var
, var
) == 0)
1664 add_comparison_var_sym(left
, left_var
, left_vsl
, comparison
, expr
, var
, vsl
);
1665 } END_FOR_EACH_PTR(tmp
);
1668 free_string(right_var
);
1671 static bool is_empty_fake_assign(struct expression
*expr
)
1673 if (!__in_fake_var_assign
)
1675 if (get_state_chunk(link_id
, expr
->right
))
1680 static void match_assign(struct expression
*expr
)
1682 struct expression
*right
;
1684 if (expr
->op
!= '=')
1686 if (__in_fake_assign
|| outside_of_function())
1689 if (is_struct(expr
->left
))
1692 if (is_self_assign(expr
))
1695 if (is_empty_fake_assign(expr
))
1698 copy_comparisons(expr
->left
, expr
->right
);
1699 add_comparison(expr
->left
, SPECIAL_EQUAL
, expr
->right
);
1701 right
= strip_expr(expr
->right
);
1702 if (right
->type
== EXPR_BINOP
)
1703 match_binop_assign(expr
);
1706 int get_comparison_strings(const char *one
, const char *two
)
1709 struct smatch_state
*state
;
1714 return UNKNOWN_COMPARISON
;
1716 if (strcmp(one
, two
) == 0)
1717 return SPECIAL_EQUAL
;
1719 if (strcmp(one
, two
) > 0) {
1720 const char *tmp
= one
;
1727 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
1728 state
= get_state(comparison_id
, buf
, NULL
);
1730 ret
= state_to_comparison(state
);
1733 ret
= flip_comparison(ret
);
1738 static int get_comparison_helper(struct expression
*a
, struct expression
*b
, bool use_extra
)
1742 int ret
= UNKNOWN_COMPARISON
;
1743 int extra
= UNKNOWN_COMPARISON
;
1745 if (a
== UNKNOWN_COMPARISON
||
1746 b
== UNKNOWN_COMPARISON
)
1747 return UNKNOWN_COMPARISON
;
1749 a
= strip_parens(a
);
1750 b
= strip_parens(b
);
1752 move_plus_to_minus(&a
, &b
);
1754 simplify_binops(&a
, &b
);
1756 one
= chunk_to_var(a
);
1759 two
= chunk_to_var(b
);
1763 ret
= get_comparison_strings(one
, two
);
1767 if (is_plus_one(a
) || is_minus_one(a
)) {
1769 one
= chunk_to_var(a
->left
);
1770 ret
= get_comparison_strings(one
, two
);
1771 } else if (is_plus_one(b
) || is_minus_one(b
)) {
1773 two
= chunk_to_var(b
->left
);
1774 ret
= get_comparison_strings(one
, two
);
1777 if (ret
== UNKNOWN_COMPARISON
)
1780 if ((is_plus_one(a
) || is_minus_one(b
)) && ret
== '<')
1782 else if ((is_minus_one(a
) || is_plus_one(b
)) && ret
== '>')
1785 ret
= UNKNOWN_COMPARISON
;
1792 extra
= comparison_from_extra(a
, b
);
1793 return comparison_intersection(ret
, extra
);
1796 int get_comparison(struct expression
*a
, struct expression
*b
)
1798 return get_comparison_helper(a
, b
, true);
1801 int get_comparison_no_extra(struct expression
*a
, struct expression
*b
)
1803 return get_comparison_helper(a
, b
, false);
1806 int possible_comparison(struct expression
*a
, int comparison
, struct expression
*b
)
1812 struct sm_state
*sm
;
1815 one
= chunk_to_var(a
);
1818 two
= chunk_to_var(b
);
1823 if (strcmp(one
, two
) == 0 && comparison
== SPECIAL_EQUAL
) {
1828 if (strcmp(one
, two
) > 0) {
1833 comparison
= flip_comparison(comparison
);
1836 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
1837 sm
= get_sm_state(comparison_id
, buf
, NULL
);
1841 FOR_EACH_PTR(sm
->possible
, sm
) {
1842 if (!sm
->state
->data
)
1844 saved
= ((struct compare_data
*)sm
->state
->data
)->comparison
;
1845 if (saved
== comparison
)
1847 if (comparison
== SPECIAL_EQUAL
&&
1848 (saved
== SPECIAL_LTE
||
1849 saved
== SPECIAL_GTE
||
1850 saved
== SPECIAL_UNSIGNED_LTE
||
1851 saved
== SPECIAL_UNSIGNED_GTE
))
1855 } END_FOR_EACH_PTR(sm
);
1864 struct state_list
*get_all_comparisons(struct expression
*expr
)
1866 struct smatch_state
*state
;
1867 struct string_list
*links
;
1868 struct state_list
*ret
= NULL
;
1869 struct sm_state
*sm
;
1872 state
= get_state_chunk(link_id
, expr
);
1875 links
= state
->data
;
1877 FOR_EACH_PTR(links
, tmp
) {
1878 sm
= get_sm_state(comparison_id
, tmp
, NULL
);
1881 // FIXME have to compare name with vsl
1882 add_ptr_list(&ret
, sm
);
1883 } END_FOR_EACH_PTR(tmp
);
1888 struct state_list
*get_all_possible_equal_comparisons(struct expression
*expr
)
1890 struct smatch_state
*state
;
1891 struct string_list
*links
;
1892 struct state_list
*ret
= NULL
;
1893 struct sm_state
*sm
;
1896 state
= get_state_chunk(link_id
, expr
);
1899 links
= state
->data
;
1901 FOR_EACH_PTR(links
, tmp
) {
1902 sm
= get_sm_state(comparison_id
, tmp
, NULL
);
1905 if (!strchr(sm
->state
->name
, '='))
1907 if (strcmp(sm
->state
->name
, "!=") == 0)
1909 add_ptr_list(&ret
, sm
);
1910 } END_FOR_EACH_PTR(tmp
);
1915 struct state_list
*get_all_possible_not_equal_comparisons(struct expression
*expr
)
1917 struct smatch_state
*state
;
1918 struct string_list
*links
;
1919 struct state_list
*ret
= NULL
;
1920 struct sm_state
*sm
;
1921 struct sm_state
*possible
;
1926 state
= get_state_chunk(link_id
, expr
);
1929 links
= state
->data
;
1931 FOR_EACH_PTR(links
, link
) {
1932 sm
= get_sm_state(comparison_id
, link
, NULL
);
1935 FOR_EACH_PTR(sm
->possible
, possible
) {
1936 if (strcmp(possible
->state
->name
, "!=") != 0)
1938 add_ptr_list(&ret
, sm
);
1940 } END_FOR_EACH_PTR(possible
);
1941 } END_FOR_EACH_PTR(link
);
1946 static void update_links_from_call(struct expression
*left
,
1948 struct expression
*right
)
1950 struct string_list
*links
;
1951 struct smatch_state
*state
;
1952 struct compare_data
*data
;
1953 struct symbol
*left_sym
, *right_sym
;
1954 char *left_var
= NULL
;
1955 char *right_var
= NULL
;
1956 struct var_sym_list
*left_vsl
;
1957 struct expression
*expr
;
1959 struct var_sym_list
*vsl
;
1963 left_var
= chunk_to_var_sym(left
, &left_sym
);
1966 left_vsl
= expr_to_vsl(left
);
1967 right_var
= chunk_to_var_sym(right
, &right_sym
);
1971 state
= get_state(link_id
, right_var
, right_sym
);
1974 links
= state
->data
;
1976 FOR_EACH_PTR(links
, tmp
) {
1977 state
= get_state(comparison_id
, tmp
, NULL
);
1978 if (!state
|| !state
->data
)
1981 comparison
= data
->comparison
;
1983 var
= data
->right_var
;
1984 vsl
= data
->right_vsl
;
1985 if (strcmp(var
, right_var
) == 0) {
1987 var
= data
->left_var
;
1988 vsl
= data
->left_vsl
;
1989 comparison
= flip_comparison(comparison
);
1991 comparison
= combine_comparisons(left_compare
, comparison
);
1994 add_comparison_var_sym(left
, left_var
, left_vsl
, comparison
, expr
, var
, vsl
);
1995 } END_FOR_EACH_PTR(tmp
);
1998 free_string(right_var
);
2001 void __add_return_comparison(struct expression
*call
, const char *range
)
2003 struct expression
*arg
;
2007 if (!str_to_comparison_arg(range
, call
, &comparison
, &arg
))
2009 snprintf(buf
, sizeof(buf
), "%s", show_comparison(comparison
));
2010 update_links_from_call(call
, comparison
, arg
);
2011 add_comparison(call
, comparison
, arg
);
2014 void __add_comparison_info(struct expression
*expr
, struct expression
*call
, const char *range
)
2016 copy_comparisons(expr
, call
);
2019 static char *get_mask_comparison(struct expression
*expr
, int ignore
)
2021 struct expression
*tmp
, *right
;
2025 /* The return value for "return foo & param;" is <= param */
2028 while ((tmp
= get_assigned_expr(expr
))) {
2029 expr
= strip_expr(tmp
);
2034 if (expr
->type
!= EXPR_BINOP
|| expr
->op
!= '&')
2037 right
= strip_expr(expr
->right
);
2038 param
= get_param_num(right
);
2039 if (param
< 0 || param
== ignore
)
2042 snprintf(buf
, sizeof(buf
), "[<=$%d]", param
);
2043 return alloc_sname(buf
);
2046 static char *range_comparison_to_param_helper(struct expression
*expr
, char starts_with
, int ignore
)
2048 struct symbol
*param
;
2051 char *ret_str
= NULL
;
2058 var
= chunk_to_var(expr
);
2063 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
2069 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
2070 compare
= get_comparison_strings(var
, buf
);
2071 if (compare
== UNKNOWN_COMPARISON
||
2072 compare
== IMPOSSIBLE_COMPARISON
)
2074 if (show_comparison(compare
)[0] != starts_with
)
2076 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_comparison(compare
), i
);
2077 ret_str
= alloc_sname(buf
);
2079 } END_FOR_EACH_PTR(param
);
2088 if (starts_with
== '<')
2089 ret_str
= get_mask_comparison(expr
, ignore
);
2093 char *name_sym_to_param_comparison(const char *name
, struct symbol
*sym
)
2095 struct symbol
*param
;
2101 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
2105 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
2106 compare
= get_comparison_strings(name
, buf
);
2107 if (compare
== UNKNOWN_COMPARISON
||
2108 compare
== IMPOSSIBLE_COMPARISON
)
2110 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_comparison(compare
), i
);
2111 return alloc_sname(buf
);
2112 } END_FOR_EACH_PTR(param
);
2117 char *expr_equal_to_param(struct expression
*expr
, int ignore
)
2119 return range_comparison_to_param_helper(expr
, '=', ignore
);
2122 char *expr_lte_to_param(struct expression
*expr
, int ignore
)
2124 return range_comparison_to_param_helper(expr
, '<', ignore
);
2127 char *expr_param_comparison(struct expression
*expr
, int ignore
)
2129 struct symbol
*param
;
2132 char *ret_str
= NULL
;
2136 var
= chunk_to_var(expr
);
2141 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, param
) {
2147 snprintf(buf
, sizeof(buf
), "%s orig", param
->ident
->name
);
2148 compare
= get_comparison_strings(var
, buf
);
2151 snprintf(buf
, sizeof(buf
), "[%s$%d]", show_comparison(compare
), i
);
2152 ret_str
= alloc_sname(buf
);
2154 } END_FOR_EACH_PTR(param
);
2161 char *get_printed_param_name(struct expression
*call
, const char *param_name
, struct symbol
*param_sym
)
2163 struct expression
*arg
;
2166 static char buf
[256];
2171 FOR_EACH_PTR(call
->args
, arg
) {
2174 name
= expr_to_var_sym(arg
, &sym
);
2177 if (sym
!= param_sym
)
2181 if (strncmp(name
, param_name
, len
) != 0)
2183 if (param_name
[len
] == '\0') {
2184 snprintf(buf
, sizeof(buf
), "$%d", i
);
2187 if (param_name
[len
] != '-')
2189 snprintf(buf
, sizeof(buf
), "$%d%s", i
, param_name
+ len
);
2191 } END_FOR_EACH_PTR(arg
);
2196 static void match_call_info(struct expression
*expr
)
2198 struct expression
*arg
;
2199 struct smatch_state
*state
;
2200 struct sm_state
*sm
;
2201 struct compare_data
*data
;
2203 struct string_list
*links
;
2205 const char *right_name
;
2211 FOR_EACH_PTR(expr
->args
, arg
) {
2214 state
= get_state_chunk(link_id
, arg
);
2218 links
= state
->data
;
2219 FOR_EACH_PTR(links
, link
) {
2220 struct var_sym_list
*right_vsl
;
2221 struct var_sym
*right_vs
;
2224 if (strstr(link
, " orig"))
2226 sm
= get_sm_state(comparison_id
, link
, NULL
);
2229 data
= sm
->state
->data
;
2231 data
->comparison
== UNKNOWN_COMPARISON
||
2232 data
->comparison
== IMPOSSIBLE_COMPARISON
)
2234 arg_name
= expr_to_var(arg
);
2239 if (strcmp(data
->left_var
, arg_name
) == 0) {
2240 comparison
= data
->comparison
;
2241 right_name
= data
->right_var
;
2242 right_vsl
= data
->right_vsl
;
2243 } else if (strcmp(data
->right_var
, arg_name
) == 0) {
2244 comparison
= flip_comparison(data
->comparison
);
2245 right_name
= data
->left_var
;
2246 right_vsl
= data
->left_vsl
;
2248 if (!right_vsl
|| ptr_list_size((struct ptr_list
*)right_vsl
) != 1)
2251 right_vs
= first_ptr_list((struct ptr_list
*)right_vsl
);
2252 if (strcmp(right_vs
->var
, right_name
) != 0)
2254 right_name
= get_printed_param_name(expr
, right_vs
->var
, right_vs
->sym
);
2257 snprintf(info_buf
, sizeof(info_buf
), "%s %s", show_comparison(comparison
), right_name
);
2258 sql_insert_caller_info(expr
, PARAM_COMPARE
, i
, "$", info_buf
);
2261 free_string(arg_name
);
2262 } END_FOR_EACH_PTR(link
);
2263 } END_FOR_EACH_PTR(arg
);
2266 static void struct_member_callback(struct expression
*call
, int param
, char *printed_name
, struct sm_state
*link_sm
)
2268 struct sm_state
*compare_sm
;
2269 struct string_list
*links
;
2271 struct compare_data
*data
;
2272 struct var_sym
*left
, *right
;
2273 static char info_buf
[256];
2274 const char *right_name
;
2276 if (strstr(printed_name
, " orig"))
2279 links
= link_sm
->state
->data
;
2280 FOR_EACH_PTR(links
, link
) {
2281 compare_sm
= get_sm_state(comparison_id
, link
, NULL
);
2284 data
= compare_sm
->state
->data
;
2285 if (!data
|| !data
->comparison
)
2288 if (ptr_list_size((struct ptr_list
*)data
->left_vsl
) != 1 ||
2289 ptr_list_size((struct ptr_list
*)data
->right_vsl
) != 1)
2291 left
= first_ptr_list((struct ptr_list
*)data
->left_vsl
);
2292 right
= first_ptr_list((struct ptr_list
*)data
->right_vsl
);
2293 if (left
->sym
== right
->sym
&&
2294 strcmp(left
->var
, right
->var
) == 0)
2297 * Both parameters link to this comparison so only
2298 * record the first one.
2300 if (left
->sym
!= link_sm
->sym
||
2301 strcmp(left
->var
, link_sm
->name
) != 0)
2304 right_name
= get_printed_param_name(call
, right
->var
, right
->sym
);
2307 snprintf(info_buf
, sizeof(info_buf
), "%s %s", show_comparison(data
->comparison
), right_name
);
2308 sql_insert_caller_info(call
, PARAM_COMPARE
, param
, printed_name
, info_buf
);
2309 } END_FOR_EACH_PTR(link
);
2312 static void print_return_value_comparison(int return_id
, char *return_ranges
, struct expression
*expr
)
2315 const char *tmp_name
;
2319 bool is_addr
= false;
2322 * TODO: This only prints == comparisons. That's probably the most
2323 * useful comparison because == max has lots of implications. But it
2324 * would be good to capture the rest as well.
2326 * This information is already in the DB but it's in the parameter math
2327 * bits and it's awkward to use it. This is is the simpler, possibly
2328 * cleaner way, but not necessarily the best, I don't know.
2333 name
= expr_to_var_sym(expr
, &sym
);
2337 param
= get_param_num_from_sym(sym
);
2340 if (param_was_set_var_sym(name
, sym
))
2343 tmp_name
= get_param_name_var_sym(name
, sym
);
2347 if (tmp_name
[0] == '&') {
2354 snprintf(info_buf
, sizeof(info_buf
), "== %s$%d%s", is_addr
? "&" : "", param
, tmp_name
);
2355 sql_insert_return_states(return_id
, return_ranges
,
2356 PARAM_COMPARE
, -1, "$", info_buf
);
2361 static void print_return_comparison(int return_id
, char *return_ranges
, struct expression
*expr
)
2363 struct sm_state
*tmp
;
2364 struct string_list
*links
;
2366 struct sm_state
*sm
;
2367 struct compare_data
*data
;
2368 struct var_sym
*left
, *right
;
2369 int left_param
, right_param
;
2371 char right_buf
[256];
2373 const char *tmp_name
;
2375 print_return_value_comparison(return_id
, return_ranges
, expr
);
2377 FOR_EACH_MY_SM(link_id
, __get_cur_stree(), tmp
) {
2378 if (get_param_num_from_sym(tmp
->sym
) < 0)
2380 links
= tmp
->state
->data
;
2381 FOR_EACH_PTR(links
, link
) {
2382 sm
= get_sm_state(comparison_id
, link
, NULL
);
2385 data
= sm
->state
->data
;
2387 data
->comparison
== UNKNOWN_COMPARISON
||
2388 data
->comparison
== IMPOSSIBLE_COMPARISON
)
2390 if (ptr_list_size((struct ptr_list
*)data
->left_vsl
) != 1 ||
2391 ptr_list_size((struct ptr_list
*)data
->right_vsl
) != 1)
2393 left
= first_ptr_list((struct ptr_list
*)data
->left_vsl
);
2394 right
= first_ptr_list((struct ptr_list
*)data
->right_vsl
);
2395 if (left
->sym
== right
->sym
&&
2396 strcmp(left
->var
, right
->var
) == 0)
2399 * Both parameters link to this comparison so only
2400 * record the first one.
2402 if (left
->sym
!= tmp
->sym
||
2403 strcmp(left
->var
, tmp
->name
) != 0)
2406 if (strstr(right
->var
, " orig"))
2409 left_param
= get_param_num_from_sym(left
->sym
);
2410 right_param
= get_param_num_from_sym(right
->sym
);
2411 if (left_param
< 0 || right_param
< 0)
2414 tmp_name
= get_param_name_var_sym(left
->var
, left
->sym
);
2417 snprintf(left_buf
, sizeof(left_buf
), "%s", tmp_name
);
2419 tmp_name
= get_param_name_var_sym(right
->var
, right
->sym
);
2420 if (!tmp_name
|| tmp_name
[0] != '$')
2422 snprintf(right_buf
, sizeof(right_buf
), "$%d%s", right_param
, tmp_name
+ 1);
2425 * FIXME: this should reject $ type variables (as
2426 * opposed to $->foo type). Those should come from
2427 * smatch_param_compare_limit.c.
2430 snprintf(info_buf
, sizeof(info_buf
), "%s %s", show_comparison(data
->comparison
), right_buf
);
2431 sql_insert_return_states(return_id
, return_ranges
,
2432 PARAM_COMPARE
, left_param
, left_buf
, info_buf
);
2433 } END_FOR_EACH_PTR(link
);
2435 } END_FOR_EACH_SM(tmp
);
2438 static int parse_comparison(char **value
, int *op
)
2446 if (**value
== '=') {
2454 *op
= SPECIAL_EQUAL
;
2459 *op
= SPECIAL_NOTEQUAL
;
2463 if (**value
== '=') {
2472 if (**value
!= ' ') {
2473 sm_perror("parsing comparison. %s", *value
);
2481 static int split_op_param_key(char *value
, int *op
, int *param
, char **key
)
2483 static char buf
[256];
2486 if (!parse_comparison(&value
, op
))
2489 snprintf(buf
, sizeof(buf
), "%s", value
);
2496 if (*param
< 0 || *param
> 99)
2508 static void db_return_comparison(struct expression
*expr
, int left_param
, char *key
, char *value
)
2510 struct expression
*left_arg
, *right_arg
;
2511 char *left_name
= NULL
;
2512 struct symbol
*left_sym
;
2513 char *right_name
= NULL
;
2514 struct symbol
*right_sym
;
2518 struct var_sym_list
*left_vsl
= NULL
, *right_vsl
= NULL
;
2520 if (left_param
== -1) {
2521 if (expr
->type
!= EXPR_ASSIGNMENT
)
2523 left_arg
= strip_expr(expr
->left
);
2525 while (expr
->type
== EXPR_ASSIGNMENT
)
2526 expr
= strip_expr(expr
->right
);
2527 if (expr
->type
!= EXPR_CALL
)
2530 while (expr
->type
== EXPR_ASSIGNMENT
)
2531 expr
= strip_expr(expr
->right
);
2532 if (expr
->type
!= EXPR_CALL
)
2535 left_arg
= get_argument_from_call_expr(expr
->args
, left_param
);
2540 if (!split_op_param_key(value
, &op
, &right_param
, &right_key
))
2543 right_arg
= get_argument_from_call_expr(expr
->args
, right_param
);
2547 left_name
= get_variable_from_key(left_arg
, key
, &left_sym
);
2548 if (!left_name
|| !left_sym
)
2551 right_name
= get_variable_from_key(right_arg
, right_key
, &right_sym
);
2552 if (!right_name
|| !right_sym
)
2555 add_var_sym(&left_vsl
, left_name
, left_sym
);
2556 add_var_sym(&right_vsl
, right_name
, right_sym
);
2558 add_comparison_var_sym(NULL
, left_name
, left_vsl
, op
, NULL
, right_name
, right_vsl
);
2561 free_string(left_name
);
2562 free_string(right_name
);
2565 int param_compare_limit_is_impossible(struct expression
*expr
, int left_param
, char *left_key
, char *value
)
2567 struct smatch_state
*state
;
2568 char *left_name
= NULL
;
2569 char *right_name
= NULL
;
2570 struct symbol
*left_sym
, *right_sym
;
2571 struct expression
*left_arg
, *right_arg
;
2578 while (expr
->type
== EXPR_ASSIGNMENT
)
2579 expr
= strip_expr(expr
->right
);
2580 if (expr
->type
!= EXPR_CALL
)
2583 if (!split_op_param_key(value
, &op
, &right_param
, &right_key
))
2586 left_arg
= get_argument_from_call_expr(expr
->args
, left_param
);
2590 right_arg
= get_argument_from_call_expr(expr
->args
, right_param
);
2594 left_name
= get_variable_from_key(left_arg
, left_key
, &left_sym
);
2595 right_name
= get_variable_from_key(right_arg
, right_key
, &right_sym
);
2596 if (!left_name
|| !right_name
)
2599 snprintf(buf
, sizeof(buf
), "%s vs %s", left_name
, right_name
);
2600 state
= get_state(comparison_id
, buf
, NULL
);
2603 state_op
= state_to_comparison(state
);
2607 if (!comparison_intersection(remove_unsigned_from_comparison(state_op
), op
))
2610 free_string(left_name
);
2611 free_string(right_name
);
2615 int impossibly_high_comparison(struct expression
*expr
)
2617 struct smatch_state
*link_state
;
2618 struct sm_state
*sm
;
2619 struct string_list
*links
;
2621 struct compare_data
*data
;
2623 link_state
= get_state_expr(link_id
, expr
);
2625 if (expr
->type
== EXPR_BINOP
&&
2626 (impossibly_high_comparison(expr
->left
) ||
2627 impossibly_high_comparison(expr
->right
)))
2632 links
= link_state
->data
;
2633 FOR_EACH_PTR(links
, link
) {
2634 sm
= get_sm_state(comparison_id
, link
, NULL
);
2637 data
= sm
->state
->data
;
2640 if (!possibly_true(data
->left
, data
->comparison
, data
->right
))
2642 } END_FOR_EACH_PTR(link
);
2647 static void free_data(struct symbol
*sym
)
2651 clear_compare_data_alloc();
2654 void register_comparison(int id
)
2657 set_dynamic_states(comparison_id
);
2658 add_hook(&save_start_states
, AFTER_DEF_HOOK
);
2659 add_unmatched_state_hook(comparison_id
, unmatched_comparison
);
2660 add_pre_merge_hook(comparison_id
, &pre_merge_hook
);
2661 add_merge_hook(comparison_id
, &merge_compare_states
);
2662 add_hook(&free_data
, AFTER_FUNC_HOOK
);
2663 add_hook(&match_call_info
, FUNCTION_CALL_HOOK
);
2664 add_split_return_callback(&print_return_comparison
);
2666 select_return_states_hook(PARAM_COMPARE
, &db_return_comparison
);
2667 add_hook(&match_preop
, OP_HOOK
);
2670 void register_comparison_late(int id
)
2672 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
2675 void register_comparison_links(int id
)
2678 db_ignore_states(link_id
);
2679 set_dynamic_states(link_id
);
2680 add_merge_hook(link_id
, &merge_links
);
2681 add_modification_hook(link_id
, &match_modify
);
2682 add_modification_hook_late(link_id
, match_inc_dec
);
2684 add_member_info_callback(link_id
, struct_member_callback
);
2687 void register_comparison_inc_dec(int id
)
2690 add_modification_hook_late(inc_dec_id
, &iter_modify
);
2693 void register_comparison_inc_dec_links(int id
)
2695 inc_dec_link_id
= id
;
2696 set_dynamic_states(inc_dec_link_id
);
2697 set_up_link_functions(inc_dec_id
, inc_dec_link_id
);
2700 static struct sm_state
*clone_partial_sm(struct sm_state
*sm
, int comparison
)
2702 struct compare_data
*data
;
2703 struct sm_state
*clone
;
2704 struct stree
*stree
;
2706 data
= sm
->state
->data
;
2708 clone
= clone_sm(sm
);
2709 clone
->state
= alloc_compare_state(data
->left
, data
->left_var
, data
->left_vsl
,
2711 data
->right
, data
->right_var
, data
->right_vsl
);
2712 free_slist(&clone
->possible
);
2713 add_possible_sm(clone
, clone
);
2715 stree
= clone_stree(sm
->pool
);
2716 overwrite_sm_state_stree(&stree
, clone
);
2717 clone
->pool
= stree
;
2722 static void create_fake_history(struct sm_state
*sm
, int op
,
2723 struct state_list
**true_stack
,
2724 struct state_list
**false_stack
)
2726 struct sm_state
*true_sm
, *false_sm
;
2727 struct compare_data
*data
;
2728 int true_comparison
;
2729 int false_comparison
;
2731 data
= sm
->state
->data
;
2733 if (is_merged(sm
) || sm
->left
|| sm
->right
)
2736 true_comparison
= comparison_intersection(data
->comparison
, op
);
2737 false_comparison
= comparison_intersection(data
->comparison
, negate_comparison(op
));
2739 true_sm
= clone_partial_sm(sm
, true_comparison
);
2740 false_sm
= clone_partial_sm(sm
, false_comparison
);
2744 sm
->right
= false_sm
;
2746 add_ptr_list(true_stack
, true_sm
);
2747 add_ptr_list(false_stack
, false_sm
);
2750 static void filter_by_sm(struct sm_state
*sm
, int op
,
2751 struct state_list
**true_stack
,
2752 struct state_list
**false_stack
,
2755 struct compare_data
*data
;
2761 data
= sm
->state
->data
;
2764 if (data
->comparison
== IMPOSSIBLE_COMPARISON
)
2768 * We want to check that "data->comparison" is totally inside "op". So
2769 * if data->comparison is < and op is <= then that's true. Or if
2770 * data->comparison is == and op is <= then that's true. But if
2771 * data->comparison is <= and op is < than that's neither true nor
2774 if (data
->comparison
== comparison_intersection(data
->comparison
, op
))
2776 if (data
->comparison
== comparison_intersection(data
->comparison
, negate_comparison(op
)))
2779 if (!is_true
&& !is_false
&& !is_merged(sm
)) {
2780 create_fake_history(sm
, op
, true_stack
, false_stack
);
2784 if (debug_implied()) {
2785 sm_msg("%s: %s: op = '%s' negated '%s'. true_intersect = '%s' false_insersect = '%s' sm = '%s'",
2788 alloc_sname(show_comparison(op
)),
2789 alloc_sname(show_comparison(negate_comparison(op
))),
2790 alloc_sname(show_comparison(comparison_intersection(data
->comparison
, op
))),
2791 alloc_sname(show_comparison(comparison_intersection(data
->comparison
, negate_comparison(op
)))),
2797 add_ptr_list(true_stack
, sm
);
2799 add_ptr_list(false_stack
, sm
);
2801 filter_by_sm(sm
->left
, op
, true_stack
, false_stack
, useful
);
2802 filter_by_sm(sm
->right
, op
, true_stack
, false_stack
, useful
);
2805 struct sm_state
*comparison_implication_hook(struct expression
*expr
,
2806 struct state_list
**true_stack
,
2807 struct state_list
**false_stack
)
2809 struct sm_state
*sm
;
2812 static char buf
[256];
2813 bool useful
= false;
2815 if (expr
->type
!= EXPR_COMPARE
)
2820 left
= expr_to_var(expr
->left
);
2821 right
= expr_to_var(expr
->right
);
2822 if (!left
|| !right
) {
2828 if (strcmp(left
, right
) > 0) {
2833 op
= flip_comparison(op
);
2836 snprintf(buf
, sizeof(buf
), "%s vs %s", left
, right
);
2837 sm
= get_sm_state(comparison_id
, buf
, NULL
);
2843 filter_by_sm(sm
, op
, true_stack
, false_stack
, &useful
);
2847 if (debug_implied())
2848 sm_msg("implications from comparison: (%s)", show_sm(sm
));