3 * smatch/smatch_comparison.c
5 * Copyright (C) 2012 Oracle.
7 * Licensed under the Open Software License version 1.1
12 * The point here is to store the relationships between two variables.
14 * To do that we create a state with the two variables in alphabetical order:
15 * ->name = "x vs y" and the state would be "<". On the false path the state
18 * Part of the trick of it is that if x or y is modified then we need to reset
19 * the state. We need to keep a list of all the states which depend on x and
20 * all the states which depend on y. The link_id code handles this.
22 * Future work: If we know that x is greater than y and y is greater than z
23 * then we know that x is greater than z.
27 #include "smatch_slist.h"
29 static int compare_id
;
32 static struct smatch_state compare_states
[] = {
37 [SPECIAL_UNSIGNED_LT
] = {
39 .data
= (void *)SPECIAL_UNSIGNED_LT
,
43 .data
= (void *)SPECIAL_LTE
,
45 [SPECIAL_UNSIGNED_LTE
] = {
47 .data
= (void *)SPECIAL_UNSIGNED_LTE
,
51 .data
= (void *)SPECIAL_EQUAL
,
53 [SPECIAL_NOTEQUAL
] = {
55 .data
= (void *)SPECIAL_NOTEQUAL
,
59 .data
= (void *)SPECIAL_GTE
,
61 [SPECIAL_UNSIGNED_GTE
] = {
63 .data
= (void *)SPECIAL_UNSIGNED_GTE
,
69 [SPECIAL_UNSIGNED_GT
] = {
71 .data
= (void *)SPECIAL_UNSIGNED_GT
,
75 static int flip_op(int op
)
82 case SPECIAL_UNSIGNED_LT
:
83 return SPECIAL_UNSIGNED_GT
;
86 case SPECIAL_UNSIGNED_LTE
:
87 return SPECIAL_UNSIGNED_GTE
;
90 case SPECIAL_NOTEQUAL
:
91 return SPECIAL_NOTEQUAL
;
94 case SPECIAL_UNSIGNED_GTE
:
95 return SPECIAL_UNSIGNED_LTE
;
98 case SPECIAL_UNSIGNED_GT
:
99 return SPECIAL_UNSIGNED_LT
;
101 sm_msg("internal smatch bug. unhandled comparison %d", op
);
106 static int falsify_op(int op
)
113 case SPECIAL_UNSIGNED_LT
:
114 return SPECIAL_UNSIGNED_GTE
;
117 case SPECIAL_UNSIGNED_LTE
:
118 return SPECIAL_UNSIGNED_GT
;
120 return SPECIAL_NOTEQUAL
;
121 case SPECIAL_NOTEQUAL
:
122 return SPECIAL_EQUAL
;
125 case SPECIAL_UNSIGNED_GTE
:
126 return SPECIAL_UNSIGNED_LT
;
129 case SPECIAL_UNSIGNED_GT
:
130 return SPECIAL_UNSIGNED_LTE
;
132 sm_msg("internal smatch bug. unhandled comparison %d", op
);
137 struct smatch_state
*alloc_link_state(struct string_list
*links
)
139 struct smatch_state
*state
;
140 static char buf
[256];
144 state
= __alloc_smatch_state(0);
147 FOR_EACH_PTR(links
, tmp
) {
149 snprintf(buf
, sizeof(buf
), "%s", tmp
);
151 snprintf(buf
, sizeof(buf
), "%s, %s", buf
, tmp
);
152 } END_FOR_EACH_PTR(tmp
);
154 state
->name
= alloc_sname(buf
);
159 static void insert_string(struct string_list
**str_list
, char *new)
163 FOR_EACH_PTR(*str_list
, tmp
) {
164 if (strcmp(tmp
, new) < 0)
166 else if (strcmp(tmp
, new) == 0) {
169 INSERT_CURRENT(new, tmp
);
172 } END_FOR_EACH_PTR(tmp
);
173 add_ptr_list(str_list
, new);
176 struct string_list
*clone_str_list(struct string_list
*orig
)
179 struct string_list
*ret
= NULL
;
181 FOR_EACH_PTR(orig
, tmp
) {
182 add_ptr_list(&ret
, tmp
);
183 } END_FOR_EACH_PTR(tmp
);
187 static struct string_list
*combine_string_lists(struct string_list
*one
, struct string_list
*two
)
189 struct string_list
*ret
;
192 ret
= clone_str_list(one
);
193 FOR_EACH_PTR(two
, tmp
) {
194 insert_string(&ret
, tmp
);
195 } END_FOR_EACH_PTR(tmp
);
199 static struct smatch_state
*merge_func(struct smatch_state
*s1
, struct smatch_state
*s2
)
201 struct smatch_state
*ret
;
202 struct string_list
*links
;
204 links
= combine_string_lists(s1
->data
, s2
->data
);
205 ret
= alloc_link_state(links
);
209 static void save_link(struct expression
*expr
, char *link
)
211 struct smatch_state
*old_state
, *new_state
;
212 struct string_list
*links
;
215 old_state
= get_state_expr(link_id
, expr
);
217 links
= clone_str_list(old_state
->data
);
221 new = alloc_sname(link
);
222 insert_string(&links
, new);
224 new_state
= alloc_link_state(links
);
225 set_state_expr(link_id
, expr
, new_state
);
228 static void clear_links(struct sm_state
*sm
)
230 struct string_list
*links
;
233 links
= sm
->state
->data
;
235 FOR_EACH_PTR(links
, tmp
) {
236 set_state(compare_id
, tmp
, NULL
, &undefined
);
237 } END_FOR_EACH_PTR(tmp
);
238 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
241 static void match_logic(struct expression
*expr
)
245 struct symbol
*left_sym
, *right_sym
;
247 struct smatch_state
*true_state
, *false_state
;
248 char state_name
[256];
250 if (expr
->type
!= EXPR_COMPARE
)
252 left
= expr_to_var_sym(expr
->left
, &left_sym
);
253 if (!left
|| !left_sym
)
255 right
= expr_to_var_sym(expr
->right
, &right_sym
);
256 if (!right
|| !right_sym
)
259 if (strcmp(left
, right
) > 0) {
263 op
= flip_op(expr
->op
);
267 false_op
= falsify_op(op
);
268 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
269 true_state
= &compare_states
[op
];
270 false_state
= &compare_states
[false_op
];
272 set_true_false_states(compare_id
, state_name
, NULL
, true_state
, false_state
);
273 save_link(expr
->left
, state_name
);
274 save_link(expr
->right
, state_name
);
280 int get_comparison(struct expression
*a
, struct expression
*b
)
285 struct smatch_state
*state
;
289 one
= expr_to_var(a
);
292 two
= expr_to_var(b
);
296 if (strcmp(one
, two
) > 0) {
304 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
305 state
= get_state(compare_id
, buf
, NULL
);
307 ret
= PTR_INT(state
->data
);
319 void register_comparison(int id
)
322 add_hook(&match_logic
, CONDITION_HOOK
);
325 void register_comparison_links(int id
)
328 add_merge_hook(link_id
, &merge_func
);
329 add_modification_hook(link_id
, &clear_links
);