estate: rename is_whole_range() to estate_is_whole()
[smatch.git] / smatch_conditions.c
blobea7c97706c18840e0a6ca79fb090b17fcee299d7
1 /*
2 * sparse/smatch_conditions.c
4 * Copyright (C) 2006,2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
11 * The simplest type of condition is
12 * if (a) { ...
14 * The next simplest kind of conditions is
15 * if (a && b) { c;
16 * In that case 'a' is true when we get to 'b' and both are true
17 * when we get to c.
19 * Or's are a little more complicated.
20 * if (a || b) { c;
21 * We know 'a' is not true when we get to 'b' but it may be true
22 * when we get to c.
24 * If we mix and's and or's that's even more complicated.
25 * if (a && b && c || a && d) { d ;
26 * 'a' is true when we evaluate 'b', and 'd'.
27 * 'b' is true when we evaluate 'c' but otherwise we don't.
29 * The other thing that complicates matters is if we negate
30 * some if conditions.
31 * if (!a) { ...
32 * Smatch has passes the un-negated version to the client and flip
33 * the true and false values internally. This makes it easier
34 * to write checks.
36 * And negations can be part of a compound.
37 * if (a && !(b || c)) { d;
38 * In that situation we multiply the negative through to simplify
39 * stuff so that we can remove the parens like this:
40 * if (a && !b && !c) { d;
42 * One other thing is that:
43 * if ((a) != 0){ ...
44 * that's basically the same as testing for just 'a' and we simplify
45 * comparisons with zero before passing it to the script.
49 #include "smatch.h"
50 #include "smatch_slist.h"
51 #include "smatch_extra.h"
52 #include "smatch_expression_stacks.h"
54 extern int __expr_stmt_count;
56 static void split_conditions(struct expression *expr);
58 static int is_logical_and(struct expression *expr)
60 if (expr->op == SPECIAL_LOGICAL_AND)
61 return 1;
62 return 0;
65 static int handle_zero_comparisons(struct expression *expr)
67 struct expression *tmp = NULL;
69 // if left is zero or right is zero
70 if (is_zero(expr->left))
71 tmp = expr->right;
72 else if (is_zero(expr->right))
73 tmp = expr->left;
74 else
75 return 0;
77 // "if (foo != 0)" is the same as "if (foo)"
78 if (expr->op == SPECIAL_NOTEQUAL) {
79 split_conditions(tmp);
80 return 1;
83 // "if (foo == 0)" is the same as "if (!foo)"
84 if (expr->op == SPECIAL_EQUAL) {
85 split_conditions(tmp);
86 __negate_cond_stacks();
87 return 1;
90 return 0;
94 * This function is for handling calls to likely/unlikely
97 static int ignore_builtin_expect(struct expression *expr)
99 if (sym_name_is("__builtin_expect", expr->fn)) {
100 split_conditions(first_ptr_list((struct ptr_list *) expr->args));
101 return 1;
103 return 0;
107 * handle_compound_stmt() is for: foo = ({blah; blah; blah; 1})
110 static void handle_compound_stmt(struct statement *stmt)
112 struct expression *expr = NULL;
113 struct statement *last;
114 struct statement *s;
116 last = last_ptr_list((struct ptr_list *)stmt->stmts);
117 if (last->type != STMT_EXPRESSION)
118 last = NULL;
119 else
120 expr = last->expression;
122 FOR_EACH_PTR(stmt->stmts, s) {
123 if (s != last)
124 __split_stmt(s);
125 } END_FOR_EACH_PTR(s);
126 split_conditions(expr);
127 return;
130 static int handle_preop(struct expression *expr)
132 struct statement *stmt;
134 if (expr->op == '!') {
135 split_conditions(expr->unop);
136 __negate_cond_stacks();
137 return 1;
139 stmt = get_expression_statement(expr);
140 if (stmt) {
141 handle_compound_stmt(stmt);
142 return 1;
144 return 0;
147 static void handle_logical(struct expression *expr)
150 * If we come to an "and" expr then:
151 * We split the left side.
152 * We keep all the current states.
153 * We split the right side.
154 * We keep all the states from both true sides.
156 * If it's an "or" expr then:
157 * We save the current slist.
158 * We split the left side.
159 * We use the false states for the right side.
160 * We split the right side.
161 * We save all the states that are the same on both sides.
164 split_conditions(expr->left);
166 if (!is_logical_and(expr))
167 __use_cond_false_states();
169 __push_cond_stacks();
171 __save_pre_cond_states();
172 split_conditions(expr->right);
173 __discard_pre_cond_states();
175 if (is_logical_and(expr))
176 __and_cond_states();
177 else
178 __or_cond_states();
180 __use_cond_true_states();
183 static struct state_list *combine(struct state_list *orig, struct state_list *fake,
184 struct state_list *new)
186 struct state_list *ret = NULL;
188 overwrite_slist(orig, &ret);
189 overwrite_slist(fake, &ret);
190 overwrite_slist(new, &ret);
191 free_slist(&new);
193 return ret;
197 * handle_select()
198 * if ((aaa()?bbb():ccc())) { ...
200 * This is almost the same as:
201 * if ((aaa() && bbb()) || (!aaa() && ccc())) { ...
203 * It's a bit complicated because we shouldn't pass aaa()
204 * to the clients more than once.
207 static void handle_select(struct expression *expr)
209 struct state_list *a_T = NULL;
210 struct state_list *a_F = NULL;
211 struct state_list *a_T_b_T = NULL;
212 struct state_list *a_T_b_F = NULL;
213 struct state_list *a_T_b_fake = NULL;
214 struct state_list *a_F_c_T = NULL;
215 struct state_list *a_F_c_F = NULL;
216 struct state_list *a_F_c_fake = NULL;
217 struct sm_state *sm;
220 * Imagine we have this: if (a ? b : c) { ...
222 * The condition is true if "a" is true and "b" is true or
223 * "a" is false and "c" is true. It's false if "a" is true
224 * and "b" is false or "a" is false and "c" is false.
226 * The variable name "a_T_b_T" stands for "a true b true" etc.
228 * But if we know "b" is true then we can simpilify things.
229 * The condition is true if "a" is true or if "a" is false and
230 * "c" is true. The only way the condition can be false is if
231 * "a" is false and "c" is false.
233 * The remaining thing is the "a_T_b_fake". When we simplify
234 * the equations we have to take into consideration that other
235 * states may have changed that don't play into the true false
236 * equation. Take the following example:
237 * if ({
238 * (flags) = __raw_local_irq_save();
239 * _spin_trylock(lock) ? 1 :
240 * ({ raw_local_irq_restore(flags); 0; });
241 * })
242 * Smatch has to record that the irq flags were restored on the
243 * false path.
247 __save_pre_cond_states();
249 split_conditions(expr->conditional);
251 a_T = __copy_cond_true_states();
252 a_F = __copy_cond_false_states();
254 __push_cond_stacks();
255 __push_fake_cur_slist();
256 split_conditions(expr->cond_true);
257 a_T_b_fake = __pop_fake_cur_slist();
258 a_T_b_T = combine(a_T, a_T_b_fake, __pop_cond_true_stack());
259 a_T_b_F = combine(a_T, a_T_b_fake, __pop_cond_false_stack());
261 __use_cond_false_states();
263 __push_cond_stacks();
264 __push_fake_cur_slist();
265 split_conditions(expr->cond_false);
266 a_F_c_fake = __pop_fake_cur_slist();
267 a_F_c_T = combine(a_F, a_F_c_fake, __pop_cond_true_stack());
268 a_F_c_F = combine(a_F, a_F_c_fake, __pop_cond_false_stack());
270 /* We have to restore the pre condition states so that
271 implied_condition_true() will use the right cur_slist */
272 __use_pre_cond_states();
274 if (implied_condition_true(expr->cond_true)) {
275 free_slist(&a_T_b_T);
276 free_slist(&a_T_b_F);
277 a_T_b_T = clone_slist(a_T);
278 overwrite_slist(a_T_b_fake, &a_T_b_T);
280 if (implied_condition_false(expr->cond_true)) {
281 free_slist(&a_T_b_T);
282 free_slist(&a_T_b_F);
283 a_T_b_F = clone_slist(a_T);
284 overwrite_slist(a_T_b_fake, &a_T_b_F);
286 if (implied_condition_true(expr->cond_false)) {
287 free_slist(&a_F_c_T);
288 free_slist(&a_F_c_F);
289 a_F_c_T = clone_slist(a_F);
290 overwrite_slist(a_F_c_fake, &a_F_c_T);
292 if (implied_condition_false(expr->cond_false)) {
293 free_slist(&a_F_c_T);
294 free_slist(&a_F_c_F);
295 a_F_c_F = clone_slist(a_F);
296 overwrite_slist(a_F_c_fake, &a_F_c_F);
299 merge_slist(&a_T_b_T, a_F_c_T);
300 merge_slist(&a_T_b_F, a_F_c_F);
302 __pop_cond_true_stack();
303 __pop_cond_false_stack();
304 __push_cond_stacks();
305 FOR_EACH_PTR(a_T_b_T, sm) {
306 __set_true_false_sm(sm, NULL);
307 } END_FOR_EACH_PTR(sm);
308 FOR_EACH_PTR(a_T_b_F, sm) {
309 __set_true_false_sm(NULL, sm);
310 } END_FOR_EACH_PTR(sm);
313 static void hackup_unsigned_compares(struct expression *expr)
315 if (expr->type != EXPR_COMPARE)
316 return;
318 switch (expr->op) {
319 case '<':
320 if (expr_unsigned(expr->left) || expr_unsigned(expr->right))
321 expr->op = SPECIAL_UNSIGNED_LT;
322 break;
323 case SPECIAL_LTE:
324 if (expr_unsigned(expr->left) || expr_unsigned(expr->right))
325 expr->op = SPECIAL_UNSIGNED_LTE;
326 break;
327 case '>':
328 if (expr_unsigned(expr->left) || expr_unsigned(expr->right))
329 expr->op = SPECIAL_UNSIGNED_GT;
330 break;
331 case SPECIAL_GTE:
332 if (expr_unsigned(expr->left) || expr_unsigned(expr->right))
333 expr->op = SPECIAL_UNSIGNED_GTE;
334 break;
338 static void split_conditions(struct expression *expr)
340 if (option_debug) {
341 char *cond = get_variable_from_expr_complex(expr, NULL);
343 sm_debug("%d in split_conditions (%s)\n", get_lineno(), cond);
344 free_string(cond);
347 expr = strip_expr(expr);
348 if (!expr)
349 return;
351 switch (expr->type) {
352 case EXPR_LOGICAL:
353 __pass_to_client(expr, LOGIC_HOOK);
354 handle_logical(expr);
355 return;
356 case EXPR_COMPARE:
357 hackup_unsigned_compares(expr);
358 if (handle_zero_comparisons(expr))
359 return;
360 break;
361 case EXPR_CALL:
362 if (ignore_builtin_expect(expr))
363 return;
364 break;
365 case EXPR_PREOP:
366 if (handle_preop(expr))
367 return;
368 break;
369 case EXPR_CONDITIONAL:
370 case EXPR_SELECT:
371 handle_select(expr);
372 return;
375 /* fixme: this should be in smatch_flow.c
376 but because of the funny stuff we do with conditions
377 it's awkward to put it there. We would need to
378 call CONDITION_HOOK in smatch_flow as well.
380 push_expression(&big_expression_stack, expr);
381 if (expr->type == EXPR_COMPARE) {
382 if (expr->left->type != EXPR_POSTOP)
383 __split_expr(expr->left);
384 if (expr->right->type != EXPR_POSTOP)
385 __split_expr(expr->right);
386 } else if (expr->type != EXPR_POSTOP) {
387 __split_expr(expr);
389 __pass_to_client(expr, CONDITION_HOOK);
390 if (expr->type == EXPR_COMPARE) {
391 if (expr->left->type == EXPR_POSTOP)
392 __split_expr(expr->left);
393 if (expr->right->type == EXPR_POSTOP)
394 __split_expr(expr->right);
395 } else if (expr->type == EXPR_POSTOP) {
396 __split_expr(expr);
398 pop_expression(&big_expression_stack);
401 static int inside_condition;
402 void __split_whole_condition(struct expression *expr)
404 sm_debug("%d in __split_whole_condition\n", get_lineno());
405 inside_condition++;
406 __save_pre_cond_states();
407 __push_cond_stacks();
408 /* it's a hack, but it's sometimes handy to have this stuff
409 on the big_expression_stack. */
410 push_expression(&big_expression_stack, expr);
411 if (expr)
412 split_conditions(expr);
413 __use_cond_states();
414 __pass_to_client(expr, WHOLE_CONDITION_HOOK);
415 pop_expression(&big_expression_stack);
416 inside_condition--;
417 sm_debug("%d done __split_whole_condition\n", get_lineno());
420 void __handle_logic(struct expression *expr)
422 sm_debug("%d in __handle_logic\n", get_lineno());
423 inside_condition++;
424 __save_pre_cond_states();
425 __push_cond_stacks();
426 /* it's a hack, but it's sometimes handy to have this stuff
427 on the big_expression_stack. */
428 push_expression(&big_expression_stack, expr);
429 if (expr)
430 split_conditions(expr);
431 __use_cond_states();
432 __pass_to_client(expr, WHOLE_CONDITION_HOOK);
433 pop_expression(&big_expression_stack);
434 __merge_false_states();
435 inside_condition--;
436 sm_debug("%d done __handle_logic\n", get_lineno());
439 int is_condition(struct expression *expr)
442 expr = strip_expr(expr);
443 if (!expr)
444 return 0;
446 switch (expr->type) {
447 case EXPR_LOGICAL:
448 case EXPR_COMPARE:
449 return 1;
450 case EXPR_PREOP:
451 if (expr->op == '!')
452 return 1;
454 return 0;
457 int __handle_condition_assigns(struct expression *expr)
459 struct expression *right;
461 right = strip_expr(expr->right);
462 if (!is_condition(expr->right))
463 return 0;
465 sm_debug("%d in __handle_condition_assigns\n", get_lineno());
466 inside_condition++;
467 __save_pre_cond_states();
468 __push_cond_stacks();
469 /* it's a hack, but it's sometimes handy to have this stuff
470 on the big_expression_stack. */
471 push_expression(&big_expression_stack, right);
472 split_conditions(right);
473 set_true_false_states_expr(SMATCH_EXTRA, expr->left,
474 alloc_estate_sval(sval_type_val(get_type(expr->left), 1)),
475 alloc_estate_sval(sval_type_val(get_type(expr->left), 0)));
476 __use_cond_states();
477 __pass_to_client(right, WHOLE_CONDITION_HOOK);
478 pop_expression(&big_expression_stack);
479 inside_condition--;
480 sm_debug("%d done __handle_condition_assigns\n", get_lineno());
482 __push_true_states();
483 __use_false_states();
484 __merge_true_states();
485 __pass_to_client(expr, ASSIGNMENT_HOOK);
486 return 1;
489 static int is_select_assign(struct expression *expr)
491 struct expression *right;
493 if (expr->op != '=')
494 return 0;
495 right = strip_expr(expr->right);
496 if (right->type == EXPR_CONDITIONAL)
497 return 1;
498 if (right->type == EXPR_SELECT)
499 return 1;
500 return 0;
503 static void set_fake_assign(struct expression *new,
504 struct expression *left, int op, struct expression *right)
507 new->pos = left->pos;
508 new->op = op;
509 new->type = EXPR_ASSIGNMENT;
510 new->left = left;
511 new->right = right;
514 int __handle_select_assigns(struct expression *expr)
516 struct expression *right;
517 struct state_list *final_states = NULL;
518 struct sm_state *sm;
519 int is_true;
520 int is_false;
522 if (!is_select_assign(expr))
523 return 0;
524 sm_debug("%d in __handle_ternary_assigns\n", get_lineno());
525 right = strip_expr(expr->right);
527 is_true = implied_condition_true(right->conditional);
528 is_false = implied_condition_false(right->conditional);
530 /* hah hah. the ultra fake out */
531 __save_pre_cond_states();
532 __split_whole_condition(right->conditional);
534 if (!is_false) {
535 struct expression fake_expr;
537 if (right->cond_true)
538 set_fake_assign(&fake_expr, expr->left, expr->op, right->cond_true);
539 else
540 set_fake_assign(&fake_expr, expr->left, expr->op, right->conditional);
541 __split_expr(&fake_expr);
542 final_states = clone_slist(__get_cur_slist());
545 __use_false_states();
546 if (!is_true) {
547 struct expression fake_expr;
549 set_fake_assign(&fake_expr, expr->left, expr->op, right->cond_false);
550 __split_expr(&fake_expr);
551 merge_slist(&final_states, __get_cur_slist());
554 __use_pre_cond_states();
556 FOR_EACH_PTR(final_states, sm) {
557 __set_sm(sm);
558 } END_FOR_EACH_PTR(sm);
560 free_slist(&final_states);
562 sm_debug("%d done __handle_ternary_assigns\n", get_lineno());
564 return 1;
567 static struct statement *split_then_return_last(struct statement *stmt)
569 struct statement *tmp;
570 struct statement *last_stmt;
572 last_stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
573 if (!last_stmt)
574 return NULL;
576 __push_scope_hooks();
577 FOR_EACH_PTR(stmt->stmts, tmp) {
578 if (tmp == last_stmt)
579 return last_stmt;
580 __split_stmt(tmp);
581 } END_FOR_EACH_PTR(tmp);
582 return NULL;
585 int __handle_expr_statement_assigns(struct expression *expr)
587 struct expression *right;
588 struct statement *stmt;
590 right = expr->right;
591 if (right->type == EXPR_PREOP && right->op == '(')
592 right = right->unop;
593 if (right->type != EXPR_STATEMENT)
594 return 0;
596 __expr_stmt_count++;
597 stmt = right->statement;
598 if (stmt->type == STMT_COMPOUND) {
599 struct statement *last_stmt;
600 struct expression fake_assign;
601 struct expression fake_expr_stmt;
603 last_stmt = split_then_return_last(stmt);
604 if (!last_stmt) {
605 __expr_stmt_count--;
606 return 0;
609 fake_expr_stmt.pos = last_stmt->pos;
610 fake_expr_stmt.type = EXPR_STATEMENT;
611 fake_expr_stmt.statement = last_stmt;
613 fake_assign.pos = last_stmt->pos;
614 fake_assign.op = expr->op;
615 fake_assign.type = EXPR_ASSIGNMENT;
616 fake_assign.left = expr->left;
617 fake_assign.right = &fake_expr_stmt;
619 __split_expr(&fake_assign);
621 __call_scope_hooks();
622 } else if (stmt->type == STMT_EXPRESSION) {
623 struct expression fake_assign;
625 fake_assign.pos = stmt->pos;
626 fake_assign.op = expr->op;
627 fake_assign.type = EXPR_ASSIGNMENT;
628 fake_assign.left = expr->left;
629 fake_assign.right = stmt->expression;
631 __split_expr(&fake_assign);
633 } else {
634 __split_stmt(stmt);
636 __expr_stmt_count--;
637 return 1;
640 int in_condition(void)
642 return inside_condition;