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_extra.h"
28 #include "smatch_slist.h"
30 static int compare_id
;
33 static struct smatch_state compare_states
[] = {
38 [SPECIAL_UNSIGNED_LT
] = {
40 .data
= (void *)SPECIAL_UNSIGNED_LT
,
44 .data
= (void *)SPECIAL_LTE
,
46 [SPECIAL_UNSIGNED_LTE
] = {
48 .data
= (void *)SPECIAL_UNSIGNED_LTE
,
52 .data
= (void *)SPECIAL_EQUAL
,
54 [SPECIAL_NOTEQUAL
] = {
56 .data
= (void *)SPECIAL_NOTEQUAL
,
60 .data
= (void *)SPECIAL_GTE
,
62 [SPECIAL_UNSIGNED_GTE
] = {
64 .data
= (void *)SPECIAL_UNSIGNED_GTE
,
70 [SPECIAL_UNSIGNED_GT
] = {
72 .data
= (void *)SPECIAL_UNSIGNED_GT
,
76 static int flip_op(int op
)
83 case SPECIAL_UNSIGNED_LT
:
84 return SPECIAL_UNSIGNED_GT
;
87 case SPECIAL_UNSIGNED_LTE
:
88 return SPECIAL_UNSIGNED_GTE
;
91 case SPECIAL_NOTEQUAL
:
92 return SPECIAL_NOTEQUAL
;
95 case SPECIAL_UNSIGNED_GTE
:
96 return SPECIAL_UNSIGNED_LTE
;
99 case SPECIAL_UNSIGNED_GT
:
100 return SPECIAL_UNSIGNED_LT
;
102 sm_msg("internal smatch bug. unhandled comparison %d", op
);
107 static int falsify_op(int op
)
114 case SPECIAL_UNSIGNED_LT
:
115 return SPECIAL_UNSIGNED_GTE
;
118 case SPECIAL_UNSIGNED_LTE
:
119 return SPECIAL_UNSIGNED_GT
;
121 return SPECIAL_NOTEQUAL
;
122 case SPECIAL_NOTEQUAL
:
123 return SPECIAL_EQUAL
;
126 case SPECIAL_UNSIGNED_GTE
:
127 return SPECIAL_UNSIGNED_LT
;
130 case SPECIAL_UNSIGNED_GT
:
131 return SPECIAL_UNSIGNED_LTE
;
133 sm_msg("internal smatch bug. unhandled comparison %d", op
);
138 struct smatch_state
*alloc_link_state(struct string_list
*links
)
140 struct smatch_state
*state
;
141 static char buf
[256];
145 state
= __alloc_smatch_state(0);
148 FOR_EACH_PTR(links
, tmp
) {
150 snprintf(buf
, sizeof(buf
), "%s", tmp
);
152 snprintf(buf
, sizeof(buf
), "%s, %s", buf
, tmp
);
153 } END_FOR_EACH_PTR(tmp
);
155 state
->name
= alloc_sname(buf
);
160 static struct smatch_state
*merge_func(struct smatch_state
*s1
, struct smatch_state
*s2
)
162 struct smatch_state
*ret
;
163 struct string_list
*links
;
165 links
= combine_string_lists(s1
->data
, s2
->data
);
166 ret
= alloc_link_state(links
);
170 static void save_link(struct expression
*expr
, char *link
)
172 struct smatch_state
*old_state
, *new_state
;
173 struct string_list
*links
;
176 old_state
= get_state_expr(link_id
, expr
);
178 links
= clone_str_list(old_state
->data
);
182 new = alloc_sname(link
);
183 insert_string(&links
, new);
185 new_state
= alloc_link_state(links
);
186 set_state_expr(link_id
, expr
, new_state
);
189 static void clear_links(struct sm_state
*sm
)
191 struct string_list
*links
;
194 links
= sm
->state
->data
;
196 FOR_EACH_PTR(links
, tmp
) {
197 set_state(compare_id
, tmp
, NULL
, &undefined
);
198 } END_FOR_EACH_PTR(tmp
);
199 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
202 static void match_logic(struct expression
*expr
)
206 struct symbol
*left_sym
, *right_sym
;
208 struct smatch_state
*true_state
, *false_state
;
209 char state_name
[256];
211 if (expr
->type
!= EXPR_COMPARE
)
213 left
= expr_to_var_sym(expr
->left
, &left_sym
);
214 if (!left
|| !left_sym
)
216 right
= expr_to_var_sym(expr
->right
, &right_sym
);
217 if (!right
|| !right_sym
)
220 if (strcmp(left
, right
) > 0) {
224 op
= flip_op(expr
->op
);
228 false_op
= falsify_op(op
);
229 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
230 true_state
= &compare_states
[op
];
231 false_state
= &compare_states
[false_op
];
233 set_true_false_states(compare_id
, state_name
, NULL
, true_state
, false_state
);
234 save_link(expr
->left
, state_name
);
235 save_link(expr
->right
, state_name
);
241 static void add_comparison(struct expression
*left
, int comparison
, struct expression
*right
)
243 char *left_name
= NULL
;
244 char *right_name
= NULL
;
245 struct symbol
*left_sym
, *right_sym
;
246 struct smatch_state
*state
;
247 char state_name
[256];
249 left_name
= expr_to_var_sym(left
, &left_sym
);
250 if (!left_name
|| !left_sym
)
252 right_name
= expr_to_var_sym(right
, &right_sym
);
253 if (!right_name
|| !right_sym
)
256 if (strcmp(left_name
, right_name
) > 0) {
257 char *tmp
= left_name
;
258 left_name
= right_name
;
260 comparison
= flip_op(comparison
);
262 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_name
, right_name
);
263 state
= &compare_states
[comparison
];
265 set_state(compare_id
, state_name
, NULL
, state
);
266 save_link(left
, state_name
);
267 save_link(right
, state_name
);
269 free_string(left_name
);
270 free_string(right_name
);
274 static void match_assign_add(struct expression
*expr
)
276 struct expression
*right
;
277 struct expression
*r_left
, *r_right
;
278 sval_t left_tmp
, right_tmp
;
280 right
= strip_expr(expr
->right
);
281 r_left
= strip_expr(right
->left
);
282 r_right
= strip_expr(right
->right
);
284 if (!is_capped(expr
->left
)) {
285 get_absolute_max(r_left
, &left_tmp
);
286 get_absolute_max(r_right
, &right_tmp
);
287 if (sval_binop_overflows(left_tmp
, '+', right_tmp
))
291 get_absolute_min(r_left
, &left_tmp
);
292 if (sval_is_negative(left_tmp
))
294 get_absolute_min(r_right
, &right_tmp
);
295 if (sval_is_negative(right_tmp
))
298 if (left_tmp
.value
== 0)
299 add_comparison(expr
->left
, SPECIAL_GTE
, r_right
);
301 add_comparison(expr
->left
, '>', r_right
);
303 if (right_tmp
.value
== 0)
304 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
306 add_comparison(expr
->left
, '>', r_left
);
309 static void match_assign_sub(struct expression
*expr
)
311 struct expression
*right
;
312 struct expression
*r_left
, *r_right
;
316 right
= strip_expr(expr
->right
);
317 r_left
= strip_expr(right
->left
);
318 r_right
= strip_expr(right
->right
);
320 if (get_absolute_min(r_right
, &min
) && sval_is_negative(min
))
323 comparison
= get_comparison(r_left
, r_right
);
325 switch (comparison
) {
328 if (implied_not_equal(r_right
, 0))
329 add_comparison(expr
->left
, '>', r_left
);
331 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
336 static void match_binop_assign(struct expression
*expr
)
338 struct expression
*right
;
340 right
= strip_expr(expr
->right
);
341 if (right
->op
== '+')
342 match_assign_add(expr
);
343 if (right
->op
== '-')
344 match_assign_sub(expr
);
347 static void match_normal_assign(struct expression
*expr
)
349 add_comparison(expr
->left
, SPECIAL_EQUAL
, expr
->right
);
352 static void match_assign(struct expression
*expr
)
354 struct expression
*right
;
356 right
= strip_expr(expr
->right
);
357 if (right
->type
== EXPR_BINOP
)
358 match_binop_assign(expr
);
360 match_normal_assign(expr
);
363 int get_comparison(struct expression
*a
, struct expression
*b
)
368 struct smatch_state
*state
;
372 one
= expr_to_var(a
);
375 two
= expr_to_var(b
);
379 if (strcmp(one
, two
) > 0) {
387 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
388 state
= get_state(compare_id
, buf
, NULL
);
390 ret
= PTR_INT(state
->data
);
402 void register_comparison(int id
)
405 add_hook(&match_logic
, CONDITION_HOOK
);
406 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
409 void register_comparison_links(int id
)
412 add_merge_hook(link_id
, &merge_func
);
413 add_modification_hook(link_id
, &clear_links
);