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 struct expression_list
*big_condition_stack
;
66 static void split_conditions(struct expression
*expr
);
68 static int is_logical_and(struct expression
*expr
)
70 if (expr
->op
== SPECIAL_LOGICAL_AND
)
75 static int handle_zero_comparisons(struct expression
*expr
)
77 struct expression
*tmp
= NULL
;
79 // if left is zero or right is zero
80 if (is_zero(expr
->left
))
82 else if (is_zero(expr
->right
))
87 // "if (foo != 0)" is the same as "if (foo)"
88 if (expr
->op
== SPECIAL_NOTEQUAL
) {
89 split_conditions(tmp
);
93 // "if (foo == 0)" is the same as "if (!foo)"
94 if (expr
->op
== SPECIAL_EQUAL
) {
95 split_conditions(tmp
);
96 __negate_cond_stacks();
104 * This function is for handling calls to likely/unlikely
107 static int ignore_builtin_expect(struct expression
*expr
)
109 if (sym_name_is("__builtin_expect", expr
->fn
)) {
110 split_conditions(first_ptr_list((struct ptr_list
*) expr
->args
));
117 * handle_compound_stmt() is for: foo = ({blah; blah; blah; 1})
120 static void handle_compound_stmt(struct statement
*stmt
)
122 struct expression
*expr
= NULL
;
123 struct statement
*last
;
126 last
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
127 if (last
->type
== STMT_LABEL
) {
128 if (last
->label_statement
&&
129 last
->label_statement
->type
== STMT_EXPRESSION
)
130 expr
= last
->label_statement
->expression
;
133 } else if (last
->type
!= STMT_EXPRESSION
) {
136 expr
= last
->expression
;
139 FOR_EACH_PTR(stmt
->stmts
, s
) {
142 } END_FOR_EACH_PTR(s
);
143 if (last
&& last
->type
== STMT_LABEL
)
144 __split_label_stmt(last
);
145 split_conditions(expr
);
148 static int handle_preop(struct expression
*expr
)
150 struct statement
*stmt
;
152 if (expr
->op
== '!') {
153 split_conditions(expr
->unop
);
154 __negate_cond_stacks();
157 stmt
= get_expression_statement(expr
);
159 handle_compound_stmt(stmt
);
165 static void handle_logical(struct expression
*expr
)
168 * If we come to an "and" expr then:
169 * We split the left side.
170 * We keep all the current states.
171 * We split the right side.
172 * We keep all the states from both true sides.
174 * If it's an "or" expr then:
175 * We save the current slist.
176 * We split the left side.
177 * We use the false states for the right side.
178 * We split the right side.
179 * We save all the states that are the same on both sides.
182 split_conditions(expr
->left
);
184 if (is_logical_and(expr
))
185 __use_cond_true_states();
187 __use_cond_false_states();
189 __push_cond_stacks();
191 __save_pre_cond_states();
192 split_conditions(expr
->right
);
193 __discard_pre_cond_states();
195 if (is_logical_and(expr
))
200 __use_cond_true_states();
203 static struct stree
*combine_strees(struct stree
*orig
, struct stree
*fake
, struct stree
*new)
205 struct stree
*ret
= NULL
;
207 overwrite_stree(orig
, &ret
);
208 overwrite_stree(fake
, &ret
);
209 overwrite_stree(new, &ret
);
217 * if ((aaa()?bbb():ccc())) { ...
219 * This is almost the same as:
220 * if ((aaa() && bbb()) || (!aaa() && ccc())) { ...
222 * It's a bit complicated because we shouldn't pass aaa()
223 * to the clients more than once.
226 static void handle_select(struct expression
*expr
)
228 struct stree
*a_T
= NULL
;
229 struct stree
*a_F
= NULL
;
230 struct stree
*a_T_b_T
= NULL
;
231 struct stree
*a_T_b_F
= NULL
;
232 struct stree
*a_T_b_fake
= NULL
;
233 struct stree
*a_F_c_T
= NULL
;
234 struct stree
*a_F_c_F
= NULL
;
235 struct stree
*a_F_c_fake
= NULL
;
240 * Imagine we have this: if (a ? b : c) { ...
242 * The condition is true if "a" is true and "b" is true or
243 * "a" is false and "c" is true. It's false if "a" is true
244 * and "b" is false or "a" is false and "c" is false.
246 * The variable name "a_T_b_T" stands for "a true b true" etc.
248 * But if we know "b" is true then we can simpilify things.
249 * The condition is true if "a" is true or if "a" is false and
250 * "c" is true. The only way the condition can be false is if
251 * "a" is false and "c" is false.
253 * The remaining thing is the "a_T_b_fake". When we simplify
254 * the equations we have to take into consideration that other
255 * states may have changed that don't play into the true false
256 * equation. Take the following example:
258 * (flags) = __raw_local_irq_save();
259 * _spin_trylock(lock) ? 1 :
260 * ({ raw_local_irq_restore(flags); 0; });
262 * Smatch has to record that the irq flags were restored on the
267 __save_pre_cond_states();
269 split_conditions(expr
->conditional
);
271 a_T
= __copy_cond_true_states();
272 a_F
= __copy_cond_false_states();
274 __use_cond_true_states();
276 __push_cond_stacks();
277 __push_fake_cur_stree();
278 split_conditions(expr
->cond_true
);
279 __process_post_op_stack();
280 a_T_b_fake
= __pop_fake_cur_stree();
281 a_T_b_T
= combine_strees(a_T
, a_T_b_fake
, __pop_cond_true_stack());
282 a_T_b_F
= combine_strees(a_T
, a_T_b_fake
, __pop_cond_false_stack());
284 __use_cond_false_states();
286 __push_cond_stacks();
287 __push_fake_cur_stree();
288 split_conditions(expr
->cond_false
);
289 a_F_c_fake
= __pop_fake_cur_stree();
290 a_F_c_T
= combine_strees(a_F
, a_F_c_fake
, __pop_cond_true_stack());
291 a_F_c_F
= combine_strees(a_F
, a_F_c_fake
, __pop_cond_false_stack());
293 /* We have to restore the pre condition states so that
294 implied_condition_true() will use the right cur_stree */
295 __use_pre_cond_states();
297 if (implied_condition_true(expr
->cond_true
)) {
298 free_stree(&a_T_b_T
);
299 free_stree(&a_T_b_F
);
300 a_T_b_T
= clone_stree(a_T
);
301 overwrite_stree(a_T_b_fake
, &a_T_b_T
);
303 if (implied_condition_false(expr
->cond_true
)) {
304 free_stree(&a_T_b_T
);
305 free_stree(&a_T_b_F
);
306 a_T_b_F
= clone_stree(a_T
);
307 overwrite_stree(a_T_b_fake
, &a_T_b_F
);
309 if (implied_condition_true(expr
->cond_false
)) {
310 free_stree(&a_F_c_T
);
311 free_stree(&a_F_c_F
);
312 a_F_c_T
= clone_stree(a_F
);
313 overwrite_stree(a_F_c_fake
, &a_F_c_T
);
315 if (implied_condition_false(expr
->cond_false
)) {
316 free_stree(&a_F_c_T
);
317 free_stree(&a_F_c_F
);
318 a_F_c_F
= clone_stree(a_F
);
319 overwrite_stree(a_F_c_fake
, &a_F_c_F
);
322 merge_stree(&a_T_b_T
, a_F_c_T
);
323 merge_stree(&a_T_b_F
, a_F_c_F
);
325 tmp
= __pop_cond_true_stack();
327 tmp
= __pop_cond_false_stack();
330 __push_cond_stacks();
331 FOR_EACH_SM(a_T_b_T
, sm
) {
332 __set_true_false_sm(sm
, NULL
);
333 } END_FOR_EACH_SM(sm
);
334 FOR_EACH_SM(a_T_b_F
, sm
) {
335 __set_true_false_sm(NULL
, sm
);
336 } END_FOR_EACH_SM(sm
);
339 free_stree(&a_T_b_fake
);
340 free_stree(&a_F_c_fake
);
341 free_stree(&a_F_c_T
);
342 free_stree(&a_F_c_F
);
343 free_stree(&a_T_b_T
);
344 free_stree(&a_T_b_F
);
349 static void handle_comma(struct expression
*expr
)
351 expr_set_parent_expr(expr
->left
, expr
);
352 expr_set_parent_expr(expr
->right
, expr
);
353 __split_expr(expr
->left
);
354 split_conditions(expr
->right
);
357 static int make_op_unsigned(int op
)
361 return SPECIAL_UNSIGNED_LT
;
363 return SPECIAL_UNSIGNED_LTE
;
365 return SPECIAL_UNSIGNED_GT
;
367 return SPECIAL_UNSIGNED_GTE
;
372 static void hackup_unsigned_compares(struct expression
*expr
)
374 if (expr
->type
!= EXPR_COMPARE
)
377 if (type_unsigned(get_type(expr
)))
378 expr
->op
= make_op_unsigned(expr
->op
);
381 static void do_condition(struct expression
*expr
)
383 __fold_in_set_states();
384 __push_fake_cur_stree();
385 __pass_to_client(expr
, CONDITION_HOOK
);
386 __fold_in_set_states();
389 static void split_conditions(struct expression
*expr
)
392 char *cond
= expr_to_str(expr
);
394 sm_msg("%d in split_conditions (%s)", get_lineno(), cond
);
398 expr
= strip_expr(expr
);
400 __fold_in_set_states();
405 * On fast paths (and also I guess some people think it's cool) people
406 * sometimes use | instead of ||. It works the same basically except
407 * that || implies a memory barrier between conditions. The easiest way
408 * to handle it is by pretending that | also has a barrier and re-using
409 * all the normal condition code. This potentially hides some bugs, but
410 * people who write code like this should just be careful or they
413 * We could potentially treat boolean bitwise & this way but that seems
414 * too complicated to deal with.
416 if (expr
->type
== EXPR_BINOP
&& expr
->op
== '|') {
417 handle_logical(expr
);
421 switch (expr
->type
) {
423 __pass_to_client(expr
, LOGIC_HOOK
);
424 handle_logical(expr
);
427 hackup_unsigned_compares(expr
);
428 if (handle_zero_comparisons(expr
))
432 if (ignore_builtin_expect(expr
))
436 if (handle_preop(expr
))
439 case EXPR_CONDITIONAL
:
448 /* fixme: this should be in smatch_flow.c
449 but because of the funny stuff we do with conditions
450 it's awkward to put it there. We would need to
451 call CONDITION_HOOK in smatch_flow as well.
453 push_expression(&big_expression_stack
, expr
);
454 push_expression(&big_condition_stack
, expr
);
456 if (expr
->type
== EXPR_COMPARE
) {
457 expr_set_parent_expr(expr
->left
, expr
);
458 expr_set_parent_expr(expr
->right
, expr
);
460 if (expr
->left
->type
!= EXPR_POSTOP
)
461 __split_expr(expr
->left
);
462 if (expr
->right
->type
!= EXPR_POSTOP
)
463 __split_expr(expr
->right
);
464 } else if (expr
->type
!= EXPR_POSTOP
) {
468 if (expr
->type
== EXPR_COMPARE
) {
469 if (expr
->left
->type
== EXPR_POSTOP
)
470 __split_expr(expr
->left
);
471 if (expr
->right
->type
== EXPR_POSTOP
)
472 __split_expr(expr
->right
);
473 } else if (expr
->type
== EXPR_POSTOP
) {
476 __push_fake_cur_stree();
477 __process_post_op_stack();
478 __fold_in_set_states();
479 pop_expression(&big_condition_stack
);
480 pop_expression(&big_expression_stack
);
483 static int inside_condition
;
484 void __split_whole_condition(struct expression
*expr
)
486 sm_debug("%d in __split_whole_condition\n", get_lineno());
488 __save_pre_cond_states();
489 __push_cond_stacks();
490 /* it's a hack, but it's sometimes handy to have this stuff
491 on the big_expression_stack. */
492 push_expression(&big_expression_stack
, expr
);
493 split_conditions(expr
);
495 __pass_to_client(expr
, WHOLE_CONDITION_HOOK
);
496 pop_expression(&big_expression_stack
);
498 sm_debug("%d done __split_whole_condition\n", get_lineno());
501 void __handle_logic(struct expression
*expr
)
503 sm_debug("%d in __handle_logic\n", get_lineno());
505 __save_pre_cond_states();
506 __push_cond_stacks();
507 /* it's a hack, but it's sometimes handy to have this stuff
508 on the big_expression_stack. */
509 push_expression(&big_expression_stack
, expr
);
511 split_conditions(expr
);
513 __pass_to_client(expr
, WHOLE_CONDITION_HOOK
);
514 pop_expression(&big_expression_stack
);
515 __merge_false_states();
517 sm_debug("%d done __handle_logic\n", get_lineno());
520 int is_condition(struct expression
*expr
)
523 expr
= strip_expr(expr
);
527 switch (expr
->type
) {
538 int __handle_condition_assigns(struct expression
*expr
)
540 struct expression
*right
;
541 struct stree
*true_stree
, *false_stree
, *fake_stree
;
546 right
= strip_expr(expr
->right
);
547 if (!is_condition(expr
->right
))
550 sm_debug("%d in __handle_condition_assigns\n", get_lineno());
552 __save_pre_cond_states();
553 __push_cond_stacks();
554 /* it's a hack, but it's sometimes handy to have this stuff
555 on the big_expression_stack. */
556 push_expression(&big_expression_stack
, right
);
557 split_conditions(right
);
558 true_stree
= __get_true_states();
559 false_stree
= __get_false_states();
561 __push_fake_cur_stree();
562 set_extra_expr_mod(expr
->left
, alloc_estate_sval(sval_type_val(get_type(expr
->left
), 1)));
563 __pass_to_client(right
, WHOLE_CONDITION_HOOK
);
565 fake_stree
= __pop_fake_cur_stree();
566 FOR_EACH_SM(fake_stree
, sm
) {
567 overwrite_sm_state_stree(&true_stree
, sm
);
568 } END_FOR_EACH_SM(sm
);
569 free_stree(&fake_stree
);
571 pop_expression(&big_expression_stack
);
574 __push_true_states();
576 __use_false_states();
577 __push_fake_cur_stree();
578 set_extra_expr_mod(expr
->left
, alloc_estate_sval(sval_type_val(get_type(expr
->left
), 0)));
580 fake_stree
= __pop_fake_cur_stree();
581 FOR_EACH_SM(fake_stree
, sm
) {
582 overwrite_sm_state_stree(&false_stree
, sm
);
583 } END_FOR_EACH_SM(sm
);
584 free_stree(&fake_stree
);
586 __merge_true_states();
587 merge_fake_stree(&true_stree
, false_stree
);
588 free_stree(&false_stree
);
589 FOR_EACH_SM(true_stree
, sm
) {
591 } END_FOR_EACH_SM(sm
);
593 __pass_to_client(expr
, ASSIGNMENT_HOOK
);
594 sm_debug("%d done __handle_condition_assigns\n", get_lineno());
598 static int is_select_assign(struct expression
*expr
)
600 struct expression
*right
;
604 right
= strip_expr(expr
->right
);
605 if (right
->type
== EXPR_CONDITIONAL
)
607 if (right
->type
== EXPR_SELECT
)
612 static void set_fake_assign(struct expression
*new,
613 struct expression
*left
, int op
, struct expression
*right
)
616 new->pos
= left
->pos
;
618 new->type
= EXPR_ASSIGNMENT
;
623 int __handle_select_assigns(struct expression
*expr
)
625 struct expression
*right
;
626 struct stree
*final_states
= NULL
;
631 if (!is_select_assign(expr
))
633 sm_debug("%d in __handle_ternary_assigns\n", get_lineno());
634 right
= strip_expr(expr
->right
);
635 __pass_to_client(right
, SELECT_HOOK
);
637 is_true
= implied_condition_true(right
->conditional
);
638 is_false
= implied_condition_false(right
->conditional
);
640 /* hah hah. the ultra fake out */
641 __save_pre_cond_states();
642 __split_whole_condition(right
->conditional
);
645 struct expression
*fake_expr
;
647 if (right
->cond_true
)
648 fake_expr
= assign_expression(expr
->left
, expr
->op
, right
->cond_true
);
650 fake_expr
= assign_expression(expr
->left
, expr
->op
, right
->conditional
);
651 __split_expr(fake_expr
);
652 final_states
= clone_stree(__get_cur_stree());
655 __use_false_states();
657 struct expression
*fake_expr
;
659 fake_expr
= assign_expression(expr
->left
, expr
->op
, right
->cond_false
);
660 __split_expr(fake_expr
);
661 merge_stree(&final_states
, __get_cur_stree());
664 __use_pre_cond_states();
666 FOR_EACH_SM(final_states
, sm
) {
668 } END_FOR_EACH_SM(sm
);
670 free_stree(&final_states
);
672 sm_debug("%d done __handle_ternary_assigns\n", get_lineno());
677 static struct statement
*split_then_return_last(struct statement
*stmt
)
679 struct statement
*tmp
;
680 struct statement
*last_stmt
;
682 last_stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
686 __push_scope_hooks();
687 FOR_EACH_PTR(stmt
->stmts
, tmp
) {
688 if (tmp
== last_stmt
) {
689 if (tmp
->type
== STMT_LABEL
) {
690 __split_label_stmt(tmp
);
691 return tmp
->label_statement
;
696 } END_FOR_EACH_PTR(tmp
);
700 int __handle_expr_statement_assigns(struct expression
*expr
)
702 struct expression
*right
;
703 struct statement
*stmt
;
706 if (right
->type
== EXPR_PREOP
&& right
->op
== '(')
708 if (right
->type
!= EXPR_STATEMENT
)
712 stmt
= right
->statement
;
713 if (stmt
->type
== STMT_COMPOUND
) {
714 struct statement
*last_stmt
;
715 struct expression
*fake_assign
;
716 struct expression fake_expr_stmt
= { .smatch_flags
= Fake
, };
718 last_stmt
= split_then_return_last(stmt
);
724 fake_expr_stmt
.pos
= last_stmt
->pos
;
725 fake_expr_stmt
.type
= EXPR_STATEMENT
;
726 fake_expr_stmt
.op
= 0;
727 fake_expr_stmt
.statement
= last_stmt
;
729 fake_assign
= assign_expression(expr
->left
, expr
->op
, &fake_expr_stmt
);
730 __split_expr(fake_assign
);
732 __pass_to_client(stmt
, STMT_HOOK_AFTER
);
733 __call_scope_hooks();
734 } else if (stmt
->type
== STMT_EXPRESSION
) {
735 struct expression
*fake_assign
;
737 fake_assign
= assign_expression(expr
->left
, expr
->op
, stmt
->expression
);
738 __split_expr(fake_assign
);
747 int in_condition(void)
749 return inside_condition
;