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 void insert_string(struct string_list
**str_list
, char *new)
164 FOR_EACH_PTR(*str_list
, tmp
) {
165 if (strcmp(tmp
, new) < 0)
167 else if (strcmp(tmp
, new) == 0) {
170 INSERT_CURRENT(new, tmp
);
173 } END_FOR_EACH_PTR(tmp
);
174 add_ptr_list(str_list
, new);
177 struct string_list
*clone_str_list(struct string_list
*orig
)
180 struct string_list
*ret
= NULL
;
182 FOR_EACH_PTR(orig
, tmp
) {
183 add_ptr_list(&ret
, tmp
);
184 } END_FOR_EACH_PTR(tmp
);
188 static struct string_list
*combine_string_lists(struct string_list
*one
, struct string_list
*two
)
190 struct string_list
*ret
;
193 ret
= clone_str_list(one
);
194 FOR_EACH_PTR(two
, tmp
) {
195 insert_string(&ret
, tmp
);
196 } END_FOR_EACH_PTR(tmp
);
200 static struct smatch_state
*merge_func(struct smatch_state
*s1
, struct smatch_state
*s2
)
202 struct smatch_state
*ret
;
203 struct string_list
*links
;
205 links
= combine_string_lists(s1
->data
, s2
->data
);
206 ret
= alloc_link_state(links
);
210 static void save_link(struct expression
*expr
, char *link
)
212 struct smatch_state
*old_state
, *new_state
;
213 struct string_list
*links
;
216 old_state
= get_state_expr(link_id
, expr
);
218 links
= clone_str_list(old_state
->data
);
222 new = alloc_sname(link
);
223 insert_string(&links
, new);
225 new_state
= alloc_link_state(links
);
226 set_state_expr(link_id
, expr
, new_state
);
229 static void clear_links(struct sm_state
*sm
)
231 struct string_list
*links
;
234 links
= sm
->state
->data
;
236 FOR_EACH_PTR(links
, tmp
) {
237 set_state(compare_id
, tmp
, NULL
, &undefined
);
238 } END_FOR_EACH_PTR(tmp
);
239 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
242 static void match_logic(struct expression
*expr
)
246 struct symbol
*left_sym
, *right_sym
;
248 struct smatch_state
*true_state
, *false_state
;
249 char state_name
[256];
251 if (expr
->type
!= EXPR_COMPARE
)
253 left
= expr_to_var_sym(expr
->left
, &left_sym
);
254 if (!left
|| !left_sym
)
256 right
= expr_to_var_sym(expr
->right
, &right_sym
);
257 if (!right
|| !right_sym
)
260 if (strcmp(left
, right
) > 0) {
264 op
= flip_op(expr
->op
);
268 false_op
= falsify_op(op
);
269 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left
, right
);
270 true_state
= &compare_states
[op
];
271 false_state
= &compare_states
[false_op
];
273 set_true_false_states(compare_id
, state_name
, NULL
, true_state
, false_state
);
274 save_link(expr
->left
, state_name
);
275 save_link(expr
->right
, state_name
);
281 static void add_comparison(struct expression
*left
, int comparison
, struct expression
*right
)
283 char *left_name
= NULL
;
284 char *right_name
= NULL
;
285 struct symbol
*left_sym
, *right_sym
;
286 struct smatch_state
*state
;
287 char state_name
[256];
289 left_name
= expr_to_var_sym(left
, &left_sym
);
290 if (!left_name
|| !left_sym
)
292 right_name
= expr_to_var_sym(right
, &right_sym
);
293 if (!right_name
|| !right_sym
)
296 if (strcmp(left_name
, right_name
) > 0) {
297 char *tmp
= left_name
;
298 left_name
= right_name
;
300 comparison
= flip_op(comparison
);
302 snprintf(state_name
, sizeof(state_name
), "%s vs %s", left_name
, right_name
);
303 state
= &compare_states
[comparison
];
305 set_state(compare_id
, state_name
, NULL
, state
);
306 save_link(left
, state_name
);
307 save_link(right
, state_name
);
309 free_string(left_name
);
310 free_string(right_name
);
314 static void match_assign_add(struct expression
*expr
)
316 struct expression
*right
;
317 struct expression
*r_left
, *r_right
;
318 sval_t left_tmp
, right_tmp
;
320 right
= strip_expr(expr
->right
);
321 r_left
= strip_expr(right
->left
);
322 r_right
= strip_expr(right
->right
);
324 if (!is_capped(expr
->left
)) {
325 get_absolute_max(r_left
, &left_tmp
);
326 get_absolute_max(r_right
, &right_tmp
);
327 if (sval_binop_overflows(left_tmp
, '+', right_tmp
))
331 get_absolute_min(r_left
, &left_tmp
);
332 if (sval_is_negative(left_tmp
))
334 get_absolute_min(r_right
, &right_tmp
);
335 if (sval_is_negative(right_tmp
))
338 if (left_tmp
.value
== 0)
339 add_comparison(expr
->left
, SPECIAL_GTE
, r_right
);
341 add_comparison(expr
->left
, '>', r_right
);
343 if (right_tmp
.value
== 0)
344 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
346 add_comparison(expr
->left
, '>', r_left
);
349 static void match_assign_sub(struct expression
*expr
)
351 struct expression
*right
;
352 struct expression
*r_left
, *r_right
;
356 right
= strip_expr(expr
->right
);
357 r_left
= strip_expr(right
->left
);
358 r_right
= strip_expr(right
->right
);
360 if (get_absolute_min(r_right
, &min
) && sval_is_negative(min
))
363 comparison
= get_comparison(r_left
, r_right
);
365 switch (comparison
) {
368 if (implied_not_equal(r_right
, 0))
369 add_comparison(expr
->left
, '>', r_left
);
371 add_comparison(expr
->left
, SPECIAL_GTE
, r_left
);
376 static void match_binop_assign(struct expression
*expr
)
378 struct expression
*right
;
380 right
= strip_expr(expr
->right
);
381 if (right
->op
== '+')
382 match_assign_add(expr
);
383 if (right
->op
== '-')
384 match_assign_sub(expr
);
387 static void match_normal_assign(struct expression
*expr
)
389 add_comparison(expr
->left
, SPECIAL_EQUAL
, expr
->right
);
392 static void match_assign(struct expression
*expr
)
394 struct expression
*right
;
396 right
= strip_expr(expr
->right
);
397 if (right
->type
== EXPR_BINOP
)
398 match_binop_assign(expr
);
400 match_normal_assign(expr
);
403 int get_comparison(struct expression
*a
, struct expression
*b
)
408 struct smatch_state
*state
;
412 one
= expr_to_var(a
);
415 two
= expr_to_var(b
);
419 if (strcmp(one
, two
) > 0) {
427 snprintf(buf
, sizeof(buf
), "%s vs %s", one
, two
);
428 state
= get_state(compare_id
, buf
, NULL
);
430 ret
= PTR_INT(state
->data
);
442 void register_comparison(int id
)
445 add_hook(&match_logic
, CONDITION_HOOK
);
446 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
449 void register_comparison_links(int id
)
452 add_merge_hook(link_id
, &merge_func
);
453 add_modification_hook(link_id
, &clear_links
);