implied: handle implications for if (({whatever; foo;}) < 0) {
[smatch.git] / smatch_conditions.c
blobd42ab6bec0534fbe08eb239f1e7366e70169b61b
1 /*
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
20 * if (a) { ...
22 * The next simplest kind of conditions is
23 * if (a && b) { c;
24 * In that case 'a' is true when we get to 'b' and both are true
25 * when we get to c.
27 * Or's are a little more complicated.
28 * if (a || b) { c;
29 * We know 'a' is not true when we get to 'b' but it may be true
30 * when we get to c.
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
38 * some if conditions.
39 * if (!a) { ...
40 * Smatch has passes the un-negated version to the client and flip
41 * the true and false values internally. This makes it easier
42 * to write checks.
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:
51 * if ((a) != 0){ ...
52 * that's basically the same as testing for just 'a' and we simplify
53 * comparisons with zero before passing it to the script.
57 #include "smatch.h"
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)
71 return 1;
72 return 0;
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))
81 tmp = expr->right;
82 else if (is_zero(expr->right))
83 tmp = expr->left;
84 else
85 return 0;
87 // "if (foo != 0)" is the same as "if (foo)"
88 if (expr->op == SPECIAL_NOTEQUAL) {
89 split_conditions(tmp);
90 return 1;
93 // "if (foo == 0)" is the same as "if (!foo)"
94 if (expr->op == SPECIAL_EQUAL) {
95 split_conditions(tmp);
96 __negate_cond_stacks();
97 return 1;
100 return 0;
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));
111 return 1;
113 return 0;
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;
124 struct statement *s;
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;
131 else
132 last = NULL;
133 } else if (last->type != STMT_EXPRESSION) {
134 last = NULL;
135 } else {
136 expr = last->expression;
139 FOR_EACH_PTR(stmt->stmts, s) {
140 if (s != last)
141 __split_stmt(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();
155 return 1;
157 stmt = get_expression_statement(expr);
158 if (stmt) {
159 handle_compound_stmt(stmt);
160 return 1;
162 return 0;
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();
186 else
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))
196 __and_cond_states();
197 else
198 __or_cond_states();
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);
210 free_stree(&new);
212 return ret;
216 * handle_select()
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;
236 struct stree *tmp;
237 struct sm_state *sm;
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:
257 * if ({
258 * (flags) = __raw_local_irq_save();
259 * _spin_trylock(lock) ? 1 :
260 * ({ raw_local_irq_restore(flags); 0; });
261 * })
262 * Smatch has to record that the irq flags were restored on the
263 * false path.
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();
326 free_stree(&tmp);
327 tmp = __pop_cond_false_stack();
328 free_stree(&tmp);
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);
337 __free_set_states();
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);
345 free_stree(&a_T);
346 free_stree(&a_F);
349 static void handle_comma(struct expression *expr)
351 set_parent_expr(expr->left, expr);
352 set_parent_expr(expr->right, expr);
353 __split_expr(expr->left);
354 split_conditions(expr->right);
357 static int make_op_unsigned(int op)
359 switch (op) {
360 case '<':
361 return SPECIAL_UNSIGNED_LT;
362 case SPECIAL_LTE:
363 return SPECIAL_UNSIGNED_LTE;
364 case '>':
365 return SPECIAL_UNSIGNED_GT;
366 case SPECIAL_GTE:
367 return SPECIAL_UNSIGNED_GTE;
369 return op;
372 static void hackup_unsigned_compares(struct expression *expr)
374 if (expr->type != EXPR_COMPARE)
375 return;
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)
391 if (option_debug) {
392 char *cond = expr_to_str(expr);
394 sm_msg("%d in split_conditions (%s)", get_lineno(), cond);
395 free_string(cond);
398 expr = strip_expr(expr);
399 if (!expr) {
400 __fold_in_set_states();
401 return;
404 switch (expr->type) {
405 case EXPR_LOGICAL:
406 __pass_to_client(expr, LOGIC_HOOK);
407 handle_logical(expr);
408 return;
409 case EXPR_COMPARE:
410 hackup_unsigned_compares(expr);
411 if (handle_zero_comparisons(expr))
412 return;
413 break;
414 case EXPR_CALL:
415 if (ignore_builtin_expect(expr))
416 return;
417 break;
418 case EXPR_PREOP:
419 if (handle_preop(expr))
420 return;
421 break;
422 case EXPR_CONDITIONAL:
423 case EXPR_SELECT:
424 handle_select(expr);
425 return;
426 case EXPR_COMMA:
427 handle_comma(expr);
428 return;
431 /* fixme: this should be in smatch_flow.c
432 but because of the funny stuff we do with conditions
433 it's awkward to put it there. We would need to
434 call CONDITION_HOOK in smatch_flow as well.
436 push_expression(&big_expression_stack, expr);
437 push_expression(&big_condition_stack, expr);
439 if (expr->type == EXPR_COMPARE) {
440 set_parent_expr(expr->left, expr);
441 set_parent_expr(expr->right, expr);
443 if (expr->left->type != EXPR_POSTOP)
444 __split_expr(expr->left);
445 if (expr->right->type != EXPR_POSTOP)
446 __split_expr(expr->right);
447 } else if (expr->type != EXPR_POSTOP) {
448 __split_expr(expr);
450 do_condition(expr);
451 if (expr->type == EXPR_COMPARE) {
452 if (expr->left->type == EXPR_POSTOP)
453 __split_expr(expr->left);
454 if (expr->right->type == EXPR_POSTOP)
455 __split_expr(expr->right);
456 } else if (expr->type == EXPR_POSTOP) {
457 __split_expr(expr);
459 __push_fake_cur_stree();
460 __process_post_op_stack();
461 __fold_in_set_states();
462 pop_expression(&big_condition_stack);
463 pop_expression(&big_expression_stack);
466 static int inside_condition;
467 void __split_whole_condition(struct expression *expr)
469 sm_debug("%d in __split_whole_condition\n", get_lineno());
470 inside_condition++;
471 __save_pre_cond_states();
472 __push_cond_stacks();
473 /* it's a hack, but it's sometimes handy to have this stuff
474 on the big_expression_stack. */
475 push_expression(&big_expression_stack, expr);
476 split_conditions(expr);
477 __use_cond_states();
478 __pass_to_client(expr, WHOLE_CONDITION_HOOK);
479 pop_expression(&big_expression_stack);
480 inside_condition--;
481 sm_debug("%d done __split_whole_condition\n", get_lineno());
484 void __handle_logic(struct expression *expr)
486 sm_debug("%d in __handle_logic\n", get_lineno());
487 inside_condition++;
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 if (expr)
494 split_conditions(expr);
495 __use_cond_states();
496 __pass_to_client(expr, WHOLE_CONDITION_HOOK);
497 pop_expression(&big_expression_stack);
498 __merge_false_states();
499 inside_condition--;
500 sm_debug("%d done __handle_logic\n", get_lineno());
503 int is_condition(struct expression *expr)
506 expr = strip_expr(expr);
507 if (!expr)
508 return 0;
510 switch (expr->type) {
511 case EXPR_LOGICAL:
512 case EXPR_COMPARE:
513 return 1;
514 case EXPR_PREOP:
515 if (expr->op == '!')
516 return 1;
518 return 0;
521 int __handle_condition_assigns(struct expression *expr)
523 struct expression *right;
524 struct stree *true_stree, *false_stree, *fake_stree;
525 struct sm_state *sm;
527 if (expr->op != '=')
528 return 0;
529 right = strip_expr(expr->right);
530 if (!is_condition(expr->right))
531 return 0;
533 sm_debug("%d in __handle_condition_assigns\n", get_lineno());
534 inside_condition++;
535 __save_pre_cond_states();
536 __push_cond_stacks();
537 /* it's a hack, but it's sometimes handy to have this stuff
538 on the big_expression_stack. */
539 push_expression(&big_expression_stack, right);
540 split_conditions(right);
541 true_stree = __get_true_states();
542 false_stree = __get_false_states();
543 __use_cond_states();
544 __push_fake_cur_stree();
545 set_extra_expr_mod(expr->left, alloc_estate_sval(sval_type_val(get_type(expr->left), 1)));
546 __pass_to_client(right, WHOLE_CONDITION_HOOK);
548 fake_stree = __pop_fake_cur_stree();
549 FOR_EACH_SM(fake_stree, sm) {
550 overwrite_sm_state_stree(&true_stree, sm);
551 } END_FOR_EACH_SM(sm);
552 free_stree(&fake_stree);
554 pop_expression(&big_expression_stack);
555 inside_condition--;
557 __push_true_states();
559 __use_false_states();
560 __push_fake_cur_stree();
561 set_extra_expr_mod(expr->left, alloc_estate_sval(sval_type_val(get_type(expr->left), 0)));
563 fake_stree = __pop_fake_cur_stree();
564 FOR_EACH_SM(fake_stree, sm) {
565 overwrite_sm_state_stree(&false_stree, sm);
566 } END_FOR_EACH_SM(sm);
567 free_stree(&fake_stree);
569 __merge_true_states();
570 merge_fake_stree(&true_stree, false_stree);
571 free_stree(&false_stree);
572 FOR_EACH_SM(true_stree, sm) {
573 __set_sm(sm);
574 } END_FOR_EACH_SM(sm);
576 __pass_to_client(expr, ASSIGNMENT_HOOK);
577 sm_debug("%d done __handle_condition_assigns\n", get_lineno());
578 return 1;
581 static int is_select_assign(struct expression *expr)
583 struct expression *right;
585 if (expr->op != '=')
586 return 0;
587 right = strip_expr(expr->right);
588 if (right->type == EXPR_CONDITIONAL)
589 return 1;
590 if (right->type == EXPR_SELECT)
591 return 1;
592 return 0;
595 static void set_fake_assign(struct expression *new,
596 struct expression *left, int op, struct expression *right)
599 new->pos = left->pos;
600 new->op = op;
601 new->type = EXPR_ASSIGNMENT;
602 new->left = left;
603 new->right = right;
606 int __handle_select_assigns(struct expression *expr)
608 struct expression *right;
609 struct stree *final_states = NULL;
610 struct sm_state *sm;
611 int is_true;
612 int is_false;
614 if (!is_select_assign(expr))
615 return 0;
616 sm_debug("%d in __handle_ternary_assigns\n", get_lineno());
617 right = strip_expr(expr->right);
619 is_true = implied_condition_true(right->conditional);
620 is_false = implied_condition_false(right->conditional);
622 /* hah hah. the ultra fake out */
623 __save_pre_cond_states();
624 __split_whole_condition(right->conditional);
626 if (!is_false) {
627 struct expression fake_expr;
629 if (right->cond_true)
630 set_fake_assign(&fake_expr, expr->left, expr->op, right->cond_true);
631 else
632 set_fake_assign(&fake_expr, expr->left, expr->op, right->conditional);
633 __split_expr(&fake_expr);
634 final_states = clone_stree(__get_cur_stree());
637 __use_false_states();
638 if (!is_true) {
639 struct expression fake_expr;
641 set_fake_assign(&fake_expr, expr->left, expr->op, right->cond_false);
642 __split_expr(&fake_expr);
643 merge_stree(&final_states, __get_cur_stree());
646 __use_pre_cond_states();
648 FOR_EACH_SM(final_states, sm) {
649 __set_sm(sm);
650 } END_FOR_EACH_SM(sm);
652 free_stree(&final_states);
654 sm_debug("%d done __handle_ternary_assigns\n", get_lineno());
656 return 1;
659 static struct statement *split_then_return_last(struct statement *stmt)
661 struct statement *tmp;
662 struct statement *last_stmt;
664 last_stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
665 if (!last_stmt)
666 return NULL;
668 __push_scope_hooks();
669 FOR_EACH_PTR(stmt->stmts, tmp) {
670 if (tmp == last_stmt) {
671 if (tmp->type == STMT_LABEL) {
672 __split_label_stmt(tmp);
673 return stmt->label_statement;
675 return last_stmt;
677 __split_stmt(tmp);
678 } END_FOR_EACH_PTR(tmp);
679 return NULL;
682 int __handle_expr_statement_assigns(struct expression *expr)
684 struct expression *right;
685 struct statement *stmt;
687 right = expr->right;
688 if (right->type == EXPR_PREOP && right->op == '(')
689 right = right->unop;
690 if (right->type != EXPR_STATEMENT)
691 return 0;
693 __expr_stmt_count++;
694 stmt = right->statement;
695 if (stmt->type == STMT_COMPOUND) {
696 struct statement *last_stmt;
697 struct expression fake_assign;
698 struct expression fake_expr_stmt;
700 last_stmt = split_then_return_last(stmt);
701 if (!last_stmt) {
702 __expr_stmt_count--;
703 return 0;
706 fake_expr_stmt.pos = last_stmt->pos;
707 fake_expr_stmt.type = EXPR_STATEMENT;
708 fake_expr_stmt.statement = last_stmt;
710 fake_assign.pos = last_stmt->pos;
711 fake_assign.op = expr->op;
712 fake_assign.type = EXPR_ASSIGNMENT;
713 fake_assign.left = expr->left;
714 fake_assign.right = &fake_expr_stmt;
716 __split_expr(&fake_assign);
718 __call_scope_hooks();
719 } else if (stmt->type == STMT_EXPRESSION) {
720 struct expression fake_assign;
722 fake_assign.pos = stmt->pos;
723 fake_assign.op = expr->op;
724 fake_assign.type = EXPR_ASSIGNMENT;
725 fake_assign.left = expr->left;
726 fake_assign.right = stmt->expression;
728 __split_expr(&fake_assign);
730 } else {
731 __split_stmt(stmt);
733 __expr_stmt_count--;
734 return 1;
737 int in_condition(void)
739 return inside_condition;