2 * Copyright (C) 2006,2008 Dan Carpenter.
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 simplest type of condition is
22 * The next simplest kind of conditions is
24 * In that case 'a' is true when we get to 'b' and both are true
27 * Or's are a little more complicated.
29 * We know 'a' is not true when we get to 'b' but it may be true
32 * If we mix and's and or's that's even more complicated.
33 * if (a && b && c || a && d) { d ;
34 * 'a' is true when we evaluate 'b', and 'd'.
35 * 'b' is true when we evaluate 'c' but otherwise we don't.
37 * The other thing that complicates matters is if we negate
40 * Smatch has passes the un-negated version to the client and flip
41 * the true and false values internally. This makes it easier
44 * And negations can be part of a compound.
45 * if (a && !(b || c)) { d;
46 * In that situation we multiply the negative through to simplify
47 * stuff so that we can remove the parens like this:
48 * if (a && !b && !c) { d;
50 * One other thing is that:
52 * that's basically the same as testing for just 'a' and we simplify
53 * comparisons with zero before passing it to the script.
58 #include "smatch_slist.h"
59 #include "smatch_extra.h"
60 #include "smatch_expression_stacks.h"
62 extern int __expr_stmt_count
;
64 static void split_conditions(struct expression
*expr
);
66 static int is_logical_and(struct expression
*expr
)
68 if (expr
->op
== SPECIAL_LOGICAL_AND
)
73 static int handle_zero_comparisons(struct expression
*expr
)
75 struct expression
*tmp
= NULL
;
77 // if left is zero or right is zero
78 if (is_zero(expr
->left
))
80 else if (is_zero(expr
->right
))
85 // "if (foo != 0)" is the same as "if (foo)"
86 if (expr
->op
== SPECIAL_NOTEQUAL
) {
87 split_conditions(tmp
);
91 // "if (foo == 0)" is the same as "if (!foo)"
92 if (expr
->op
== SPECIAL_EQUAL
) {
93 split_conditions(tmp
);
94 __negate_cond_stacks();
102 * This function is for handling calls to likely/unlikely
105 static int ignore_builtin_expect(struct expression
*expr
)
107 if (sym_name_is("__builtin_expect", expr
->fn
)) {
108 split_conditions(first_ptr_list((struct ptr_list
*) expr
->args
));
115 * handle_compound_stmt() is for: foo = ({blah; blah; blah; 1})
118 static void handle_compound_stmt(struct statement
*stmt
)
120 struct expression
*expr
= NULL
;
121 struct statement
*last
;
124 last
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
125 if (last
->type
!= STMT_EXPRESSION
)
128 expr
= last
->expression
;
130 FOR_EACH_PTR(stmt
->stmts
, s
) {
133 } END_FOR_EACH_PTR(s
);
134 split_conditions(expr
);
138 static int handle_preop(struct expression
*expr
)
140 struct statement
*stmt
;
142 if (expr
->op
== '!') {
143 split_conditions(expr
->unop
);
144 __negate_cond_stacks();
147 stmt
= get_expression_statement(expr
);
149 handle_compound_stmt(stmt
);
155 static void handle_logical(struct expression
*expr
)
158 * If we come to an "and" expr then:
159 * We split the left side.
160 * We keep all the current states.
161 * We split the right side.
162 * We keep all the states from both true sides.
164 * If it's an "or" expr then:
165 * We save the current slist.
166 * We split the left side.
167 * We use the false states for the right side.
168 * We split the right side.
169 * We save all the states that are the same on both sides.
172 split_conditions(expr
->left
);
173 __process_post_op_stack();
175 if (!is_logical_and(expr
))
176 __use_cond_false_states();
178 __push_cond_stacks();
180 __save_pre_cond_states();
181 split_conditions(expr
->right
);
182 __process_post_op_stack();
183 __discard_pre_cond_states();
185 if (is_logical_and(expr
))
190 __use_cond_true_states();
193 static struct state_list
*combine(struct state_list
*orig
, struct state_list
*fake
,
194 struct state_list
*new)
196 struct state_list
*ret
= NULL
;
198 overwrite_slist(orig
, &ret
);
199 overwrite_slist(fake
, &ret
);
200 overwrite_slist(new, &ret
);
208 * if ((aaa()?bbb():ccc())) { ...
210 * This is almost the same as:
211 * if ((aaa() && bbb()) || (!aaa() && ccc())) { ...
213 * It's a bit complicated because we shouldn't pass aaa()
214 * to the clients more than once.
217 static void handle_select(struct expression
*expr
)
219 struct state_list
*a_T
= NULL
;
220 struct state_list
*a_F
= NULL
;
221 struct state_list
*a_T_b_T
= NULL
;
222 struct state_list
*a_T_b_F
= NULL
;
223 struct state_list
*a_T_b_fake
= NULL
;
224 struct state_list
*a_F_c_T
= NULL
;
225 struct state_list
*a_F_c_F
= NULL
;
226 struct state_list
*a_F_c_fake
= NULL
;
230 * Imagine we have this: if (a ? b : c) { ...
232 * The condition is true if "a" is true and "b" is true or
233 * "a" is false and "c" is true. It's false if "a" is true
234 * and "b" is false or "a" is false and "c" is false.
236 * The variable name "a_T_b_T" stands for "a true b true" etc.
238 * But if we know "b" is true then we can simpilify things.
239 * The condition is true if "a" is true or if "a" is false and
240 * "c" is true. The only way the condition can be false is if
241 * "a" is false and "c" is false.
243 * The remaining thing is the "a_T_b_fake". When we simplify
244 * the equations we have to take into consideration that other
245 * states may have changed that don't play into the true false
246 * equation. Take the following example:
248 * (flags) = __raw_local_irq_save();
249 * _spin_trylock(lock) ? 1 :
250 * ({ raw_local_irq_restore(flags); 0; });
252 * Smatch has to record that the irq flags were restored on the
257 __save_pre_cond_states();
259 split_conditions(expr
->conditional
);
261 a_T
= __copy_cond_true_states();
262 a_F
= __copy_cond_false_states();
264 __push_cond_stacks();
265 __push_fake_cur_slist();
266 split_conditions(expr
->cond_true
);
267 __process_post_op_stack();
268 a_T_b_fake
= __pop_fake_cur_slist();
269 a_T_b_T
= combine(a_T
, a_T_b_fake
, __pop_cond_true_stack());
270 a_T_b_F
= combine(a_T
, a_T_b_fake
, __pop_cond_false_stack());
272 __use_cond_false_states();
274 __push_cond_stacks();
275 __push_fake_cur_slist();
276 split_conditions(expr
->cond_false
);
277 a_F_c_fake
= __pop_fake_cur_slist();
278 a_F_c_T
= combine(a_F
, a_F_c_fake
, __pop_cond_true_stack());
279 a_F_c_F
= combine(a_F
, a_F_c_fake
, __pop_cond_false_stack());
281 /* We have to restore the pre condition states so that
282 implied_condition_true() will use the right cur_slist */
283 __use_pre_cond_states();
285 if (implied_condition_true(expr
->cond_true
)) {
286 free_slist(&a_T_b_T
);
287 free_slist(&a_T_b_F
);
288 a_T_b_T
= clone_slist(a_T
);
289 overwrite_slist(a_T_b_fake
, &a_T_b_T
);
291 if (implied_condition_false(expr
->cond_true
)) {
292 free_slist(&a_T_b_T
);
293 free_slist(&a_T_b_F
);
294 a_T_b_F
= clone_slist(a_T
);
295 overwrite_slist(a_T_b_fake
, &a_T_b_F
);
297 if (implied_condition_true(expr
->cond_false
)) {
298 free_slist(&a_F_c_T
);
299 free_slist(&a_F_c_F
);
300 a_F_c_T
= clone_slist(a_F
);
301 overwrite_slist(a_F_c_fake
, &a_F_c_T
);
303 if (implied_condition_false(expr
->cond_false
)) {
304 free_slist(&a_F_c_T
);
305 free_slist(&a_F_c_F
);
306 a_F_c_F
= clone_slist(a_F
);
307 overwrite_slist(a_F_c_fake
, &a_F_c_F
);
310 merge_slist(&a_T_b_T
, a_F_c_T
);
311 merge_slist(&a_T_b_F
, a_F_c_F
);
313 __pop_cond_true_stack();
314 __pop_cond_false_stack();
315 __push_cond_stacks();
316 FOR_EACH_PTR(a_T_b_T
, sm
) {
317 __set_true_false_sm(sm
, NULL
);
318 } END_FOR_EACH_PTR(sm
);
319 FOR_EACH_PTR(a_T_b_F
, sm
) {
320 __set_true_false_sm(NULL
, sm
);
321 } END_FOR_EACH_PTR(sm
);
323 free_slist(&a_T_b_fake
);
324 free_slist(&a_F_c_fake
);
327 static int make_op_unsigned(int op
)
331 return SPECIAL_UNSIGNED_LT
;
333 return SPECIAL_UNSIGNED_LTE
;
335 return SPECIAL_UNSIGNED_GT
;
337 return SPECIAL_UNSIGNED_GTE
;
342 static void hackup_unsigned_compares(struct expression
*expr
)
344 if (expr
->type
!= EXPR_COMPARE
)
347 if (type_unsigned(get_type(expr
)))
348 expr
->op
= make_op_unsigned(expr
->op
);
351 static void split_conditions(struct expression
*expr
)
354 char *cond
= expr_to_str(expr
);
356 sm_debug("%d in split_conditions (%s)\n", get_lineno(), cond
);
360 expr
= strip_expr(expr
);
364 switch (expr
->type
) {
366 __pass_to_client(expr
, LOGIC_HOOK
);
367 handle_logical(expr
);
370 hackup_unsigned_compares(expr
);
371 if (handle_zero_comparisons(expr
))
375 if (ignore_builtin_expect(expr
))
379 if (handle_preop(expr
))
382 case EXPR_CONDITIONAL
:
388 /* fixme: this should be in smatch_flow.c
389 but because of the funny stuff we do with conditions
390 it's awkward to put it there. We would need to
391 call CONDITION_HOOK in smatch_flow as well.
393 push_expression(&big_expression_stack
, expr
);
394 if (expr
->type
== EXPR_COMPARE
) {
395 if (expr
->left
->type
!= EXPR_POSTOP
)
396 __split_expr(expr
->left
);
397 if (expr
->right
->type
!= EXPR_POSTOP
)
398 __split_expr(expr
->right
);
399 } else if (expr
->type
!= EXPR_POSTOP
) {
402 __pass_to_client(expr
, CONDITION_HOOK
);
403 if (expr
->type
== EXPR_COMPARE
) {
404 if (expr
->left
->type
== EXPR_POSTOP
)
405 __split_expr(expr
->left
);
406 if (expr
->right
->type
== EXPR_POSTOP
)
407 __split_expr(expr
->right
);
408 } else if (expr
->type
== EXPR_POSTOP
) {
411 __process_post_op_stack();
412 pop_expression(&big_expression_stack
);
415 static int inside_condition
;
416 void __split_whole_condition(struct expression
*expr
)
418 sm_debug("%d in __split_whole_condition\n", get_lineno());
420 __save_pre_cond_states();
421 __push_cond_stacks();
422 /* it's a hack, but it's sometimes handy to have this stuff
423 on the big_expression_stack. */
424 push_expression(&big_expression_stack
, expr
);
426 split_conditions(expr
);
428 __pass_to_client(expr
, WHOLE_CONDITION_HOOK
);
429 pop_expression(&big_expression_stack
);
431 sm_debug("%d done __split_whole_condition\n", get_lineno());
434 void __handle_logic(struct expression
*expr
)
436 sm_debug("%d in __handle_logic\n", get_lineno());
438 __save_pre_cond_states();
439 __push_cond_stacks();
440 /* it's a hack, but it's sometimes handy to have this stuff
441 on the big_expression_stack. */
442 push_expression(&big_expression_stack
, expr
);
444 split_conditions(expr
);
446 __pass_to_client(expr
, WHOLE_CONDITION_HOOK
);
447 pop_expression(&big_expression_stack
);
448 __merge_false_states();
450 sm_debug("%d done __handle_logic\n", get_lineno());
453 int is_condition(struct expression
*expr
)
456 expr
= strip_expr(expr
);
460 switch (expr
->type
) {
471 int __handle_condition_assigns(struct expression
*expr
)
473 struct expression
*right
;
475 right
= strip_expr(expr
->right
);
476 if (!is_condition(expr
->right
))
479 sm_debug("%d in __handle_condition_assigns\n", get_lineno());
481 __save_pre_cond_states();
482 __push_cond_stacks();
483 /* it's a hack, but it's sometimes handy to have this stuff
484 on the big_expression_stack. */
485 push_expression(&big_expression_stack
, right
);
486 split_conditions(right
);
488 set_extra_expr_mod(expr
->left
, alloc_estate_sval(sval_type_val(get_type(expr
->left
), 1)));
489 __pass_to_client(right
, WHOLE_CONDITION_HOOK
);
490 pop_expression(&big_expression_stack
);
492 sm_debug("%d done __handle_condition_assigns\n", get_lineno());
494 __push_true_states();
495 __use_false_states();
496 set_extra_expr_mod(expr
->left
, alloc_estate_sval(sval_type_val(get_type(expr
->left
), 0)));
497 __merge_true_states();
498 __pass_to_client(expr
, ASSIGNMENT_HOOK
);
502 static int is_select_assign(struct expression
*expr
)
504 struct expression
*right
;
508 right
= strip_expr(expr
->right
);
509 if (right
->type
== EXPR_CONDITIONAL
)
511 if (right
->type
== EXPR_SELECT
)
516 static void set_fake_assign(struct expression
*new,
517 struct expression
*left
, int op
, struct expression
*right
)
520 new->pos
= left
->pos
;
522 new->type
= EXPR_ASSIGNMENT
;
527 int __handle_select_assigns(struct expression
*expr
)
529 struct expression
*right
;
530 struct state_list
*final_states
= NULL
;
535 if (!is_select_assign(expr
))
537 sm_debug("%d in __handle_ternary_assigns\n", get_lineno());
538 right
= strip_expr(expr
->right
);
540 is_true
= implied_condition_true(right
->conditional
);
541 is_false
= implied_condition_false(right
->conditional
);
543 /* hah hah. the ultra fake out */
544 __save_pre_cond_states();
545 __split_whole_condition(right
->conditional
);
548 struct expression fake_expr
;
550 if (right
->cond_true
)
551 set_fake_assign(&fake_expr
, expr
->left
, expr
->op
, right
->cond_true
);
553 set_fake_assign(&fake_expr
, expr
->left
, expr
->op
, right
->conditional
);
554 __split_expr(&fake_expr
);
555 final_states
= clone_slist(__get_cur_slist());
558 __use_false_states();
560 struct expression fake_expr
;
562 set_fake_assign(&fake_expr
, expr
->left
, expr
->op
, right
->cond_false
);
563 __split_expr(&fake_expr
);
564 merge_slist(&final_states
, __get_cur_slist());
567 __use_pre_cond_states();
569 FOR_EACH_PTR(final_states
, sm
) {
571 } END_FOR_EACH_PTR(sm
);
573 free_slist(&final_states
);
575 sm_debug("%d done __handle_ternary_assigns\n", get_lineno());
580 static struct statement
*split_then_return_last(struct statement
*stmt
)
582 struct statement
*tmp
;
583 struct statement
*last_stmt
;
585 last_stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
589 __push_scope_hooks();
590 FOR_EACH_PTR(stmt
->stmts
, tmp
) {
591 if (tmp
== last_stmt
)
594 } END_FOR_EACH_PTR(tmp
);
598 int __handle_expr_statement_assigns(struct expression
*expr
)
600 struct expression
*right
;
601 struct statement
*stmt
;
604 if (right
->type
== EXPR_PREOP
&& right
->op
== '(')
606 if (right
->type
!= EXPR_STATEMENT
)
610 stmt
= right
->statement
;
611 if (stmt
->type
== STMT_COMPOUND
) {
612 struct statement
*last_stmt
;
613 struct expression fake_assign
;
614 struct expression fake_expr_stmt
;
616 last_stmt
= split_then_return_last(stmt
);
622 fake_expr_stmt
.pos
= last_stmt
->pos
;
623 fake_expr_stmt
.type
= EXPR_STATEMENT
;
624 fake_expr_stmt
.statement
= last_stmt
;
626 fake_assign
.pos
= last_stmt
->pos
;
627 fake_assign
.op
= expr
->op
;
628 fake_assign
.type
= EXPR_ASSIGNMENT
;
629 fake_assign
.left
= expr
->left
;
630 fake_assign
.right
= &fake_expr_stmt
;
632 __split_expr(&fake_assign
);
634 __call_scope_hooks();
635 } else if (stmt
->type
== STMT_EXPRESSION
) {
636 struct expression fake_assign
;
638 fake_assign
.pos
= stmt
->pos
;
639 fake_assign
.op
= expr
->op
;
640 fake_assign
.type
= EXPR_ASSIGNMENT
;
641 fake_assign
.left
= expr
->left
;
642 fake_assign
.right
= stmt
->expression
;
644 __split_expr(&fake_assign
);
653 int in_condition(void)
655 return inside_condition
;