sval: move cast_rl() into parse_value_ranges_type()
[smatch.git] / smatch_math.c
blob775787854bb72f3e3395069aabc5b47ef65d34ee
1 /*
2 * smatch/smatch_math.c
4 * Copyright (C) 2010 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
10 #include "smatch.h"
11 #include "smatch_slist.h"
12 #include "smatch_extra.h"
14 static sval_t _get_value(struct expression *expr, int *undefined, int implied);
15 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied);
17 #define BOGUS 12345
19 static sval_t zero = {.type = &int_ctype, .value = 0};
20 static sval_t one = {.type = &int_ctype, .value = 1};
21 static sval_t bogus = {.type = &int_ctype, .value = BOGUS};
23 #define NOTIMPLIED 0
24 #define IMPLIED 1
25 #define IMPLIED_MIN 2
26 #define IMPLIED_MAX 3
27 #define FUZZYMAX 4
28 #define FUZZYMIN 5
29 #define ABSOLUTE_MIN 6
30 #define ABSOLUTE_MAX 7
31 #define HARD_MAX 8
33 static int opposite_implied(int implied)
35 if (implied == IMPLIED_MIN)
36 return IMPLIED_MAX;
37 if (implied == IMPLIED_MAX)
38 return IMPLIED_MIN;
39 if (implied == ABSOLUTE_MIN)
40 return ABSOLUTE_MAX;
41 if (implied == ABSOLUTE_MAX)
42 return ABSOLUTE_MIN;
43 return implied;
46 static int last_stmt_sval(struct statement *stmt, sval_t *sval)
48 struct expression *expr;
50 if (!stmt)
51 return 0;
53 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
54 if (stmt->type != STMT_EXPRESSION)
55 return 0;
56 expr = stmt->expression;
57 if (!get_value(expr, sval))
58 return 0;
59 return 1;
62 static sval_t handle_expression_statement(struct expression *expr, int *undefined, int implied)
64 struct statement *stmt;
65 sval_t ret;
67 stmt = get_expression_statement(expr);
68 if (!last_stmt_sval(stmt, &ret)) {
69 *undefined = 1;
70 ret.value = BOGUS;
73 return ret;
76 static sval_t handle_ampersand(int *undefined, int implied)
78 sval_t ret;
80 ret.type = &ptr_ctype;
81 ret.value = BOGUS;
83 if (implied == IMPLIED_MIN || implied == FUZZYMIN || implied == ABSOLUTE_MIN)
84 return valid_ptr_min_sval;
85 if (implied == IMPLIED_MAX || implied == FUZZYMAX || implied == ABSOLUTE_MAX)
86 return valid_ptr_max_sval;
88 *undefined = 1;
89 return ret;
92 static sval_t handle_preop(struct expression *expr, int *undefined, int implied)
94 sval_t ret;
96 switch (expr->op) {
97 case '&':
98 ret = handle_ampersand(undefined, implied);
99 break;
100 case '!':
101 ret = _get_value(expr->unop, undefined, implied);
102 ret = sval_preop(ret, '!');
103 break;
104 case '~':
105 ret = _get_value(expr->unop, undefined, implied);
106 ret = sval_preop(ret, '~');
107 ret = sval_cast(get_type(expr->unop), ret);
108 break;
109 case '-':
110 ret = _get_value(expr->unop, undefined, implied);
111 ret = sval_preop(ret, '-');
112 break;
113 case '*':
114 ret = _get_implied_value(expr, undefined, implied);
115 break;
116 case '(':
117 ret = handle_expression_statement(expr, undefined, implied);
118 break;
119 default:
120 *undefined = 1;
121 ret = sval_blank(expr);
123 ret = sval_cast(get_type(expr), ret);
124 return ret;
127 static sval_t handle_divide(struct expression *expr, int *undefined, int implied)
129 sval_t left, right;
131 left = _get_value(expr->left, undefined, implied);
132 right = _get_value(expr->right, undefined, opposite_implied(implied));
134 if (right.value == 0) {
135 *undefined = 1;
136 return bogus;
139 return sval_binop(left, '/', right);
142 static sval_t handle_subtract(struct expression *expr, int *undefined, int implied)
144 sval_t left, right;
146 left = _get_value(expr->left, undefined, implied);
147 right = _get_value(expr->right, undefined, opposite_implied(implied));
149 return sval_binop(left, '-', right);
152 static sval_t handle_binop(struct expression *expr, int *undefined, int implied)
154 sval_t left, right;
155 sval_t ret = {.type = &int_ctype, .value = 123456};
156 int local_undef = 0;
158 switch (expr->op) {
159 case '%':
160 left = _get_value(expr->left, &local_undef, implied);
161 if (local_undef) {
162 if (implied == ABSOLUTE_MIN) {
163 ret = sval_blank(expr->left);
164 ret.value = 0;
165 return ret;
167 if (implied != ABSOLUTE_MAX)
168 *undefined = 1;
169 if (!get_absolute_max(expr->left, &left))
170 *undefined = 1;
172 right = _get_value(expr->right, undefined, implied);
173 if (right.value == 0)
174 *undefined = 1;
175 if (*undefined)
176 return bogus;
177 return sval_binop(left, '%', right);
179 case '&':
180 left = _get_value(expr->left, &local_undef, implied);
181 if (local_undef) {
182 if (implied == ABSOLUTE_MIN) {
183 ret = sval_blank(expr->left);
184 ret.value = 0;
185 return ret;
187 if (implied != ABSOLUTE_MAX)
188 *undefined = 1;
189 if (!get_absolute_max(expr->left, &left))
190 *undefined = 1;
192 right = _get_value(expr->right, undefined, implied);
193 if (*undefined)
194 return bogus;
195 return sval_binop(left, '&', right);
197 case SPECIAL_RIGHTSHIFT:
198 left = _get_value(expr->left, &local_undef, implied);
199 if (local_undef) {
200 if (implied == ABSOLUTE_MIN) {
201 ret = sval_blank(expr->left);
202 ret.value = 0;
203 return ret;
205 if (implied != ABSOLUTE_MAX)
206 *undefined = 1;
207 if (!get_absolute_max(expr->left, &left))
208 *undefined = 1;
210 right = _get_value(expr->right, undefined, implied);
211 if (*undefined)
212 return bogus;
213 return sval_binop(left, SPECIAL_RIGHTSHIFT, right);
216 left = _get_value(expr->left, undefined, implied);
217 right = _get_value(expr->right, undefined, implied);
219 if (*undefined)
220 return bogus;
222 switch (expr->op) {
223 case '/':
224 return handle_divide(expr, undefined, implied);
225 case '%':
226 if (right.value == 0) {
227 *undefined = 1;
228 return bogus;
229 } else {
230 return sval_binop(left, '%', right);
232 case '-':
233 ret = handle_subtract(expr, undefined, implied);
234 break;
235 default:
236 ret = sval_binop(left, expr->op, right);
238 return ret;
241 static int do_comparison(struct expression *expr)
243 struct range_list *left_ranges = NULL;
244 struct range_list *right_ranges = NULL;
245 int poss_true, poss_false;
247 get_implied_range_list(expr->left, &left_ranges);
248 get_implied_range_list(expr->right, &right_ranges);
250 poss_true = possibly_true_range_lists(left_ranges, expr->op, right_ranges);
251 poss_false = possibly_false_range_lists(left_ranges, expr->op, right_ranges);
253 free_range_list(&left_ranges);
254 free_range_list(&right_ranges);
256 if (!poss_true && !poss_false)
257 return 0;
258 if (poss_true && !poss_false)
259 return 1;
260 if (!poss_true && poss_false)
261 return 2;
262 return 3;
265 static sval_t handle_comparison(struct expression *expr, int *undefined, int implied)
267 sval_t left, right;
268 int res;
270 if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
271 struct data_range tmp_left, tmp_right;
273 tmp_left.min = left;
274 tmp_left.max = left;
275 tmp_right.min = right;
276 tmp_right.max = right;
277 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
278 return one;
279 return zero;
282 if (implied == NOTIMPLIED) {
283 *undefined = 1;
284 return bogus;
287 res = do_comparison(expr);
288 if (res == 1)
289 return one;
290 if (res == 2)
291 return zero;
293 if (implied == IMPLIED_MIN || implied == FUZZYMIN || implied == ABSOLUTE_MIN)
294 return zero;
295 if (implied == IMPLIED_MAX || implied == FUZZYMAX || implied == ABSOLUTE_MAX)
296 return one;
298 *undefined = 1;
299 return bogus;
302 static sval_t handle_logical(struct expression *expr, int *undefined, int implied)
304 sval_t left, right;
306 if ((implied == NOTIMPLIED && get_value(expr->left, &left) &&
307 get_value(expr->right, &right)) ||
308 (implied != NOTIMPLIED && get_implied_value(expr->left, &left) &&
309 get_implied_value(expr->right, &right))) {
310 switch (expr->op) {
311 case SPECIAL_LOGICAL_OR:
312 if (left.value || right.value)
313 return one;
314 return zero;
315 case SPECIAL_LOGICAL_AND:
316 if (left.value && right.value)
317 return one;
318 return zero;
319 default:
320 *undefined = 1;
321 return bogus;
325 if (implied == IMPLIED_MIN || implied == FUZZYMIN || implied == ABSOLUTE_MIN)
326 return zero;
327 if (implied == IMPLIED_MAX || implied == FUZZYMAX || implied == ABSOLUTE_MAX)
328 return one;
330 *undefined = 1;
331 return bogus;
334 static sval_t handle_conditional(struct expression *expr, int *undefined, int implied)
336 if (known_condition_true(expr->conditional))
337 return _get_value(expr->cond_true, undefined, implied);
338 if (known_condition_false(expr->conditional))
339 return _get_value(expr->cond_false, undefined, implied);
341 if (implied == NOTIMPLIED) {
342 *undefined = 1;
343 return bogus;
346 if (implied_condition_true(expr->conditional))
347 return _get_value(expr->cond_true, undefined, implied);
348 if (implied_condition_false(expr->conditional))
349 return _get_value(expr->cond_false, undefined, implied);
351 *undefined = 1;
352 return bogus;
355 static int get_implied_value_helper(struct expression *expr, sval_t *sval, int implied)
357 struct smatch_state *state;
358 struct symbol *sym;
359 char *name;
361 /* fixme: this should return the casted value */
363 expr = strip_expr(expr);
365 if (get_value(expr, sval))
366 return 1;
368 name = get_variable_from_expr(expr, &sym);
369 if (!name)
370 return 0;
371 *sval = sval_blank(expr);
372 state = get_state(SMATCH_EXTRA, name, sym);
373 free_string(name);
374 if (!state || !state->data)
375 return 0;
376 if (implied == IMPLIED) {
377 if (estate_get_single_value(state, sval))
378 return 1;
379 return 0;
381 if (implied == HARD_MAX) {
382 if (estate_get_hard_max(state, sval))
383 return 1;
384 return 0;
386 if (implied == IMPLIED_MAX) {
387 *sval = estate_max(state);
388 if (sval_is_max(*sval)) /* this means just guessing. fixme. not really */
389 return 0;
390 return 1;
392 *sval = estate_min(state);
393 if (sval_is_min(*sval)) /* fixme */
394 return 0;
395 return 1;
398 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
400 struct sm_state *sm;
401 struct sm_state *tmp;
402 sval_t sval;
404 if (get_hard_max(expr, &sval)) {
405 *max = sval;
406 return 1;
409 sm = get_sm_state_expr(SMATCH_EXTRA, expr);
410 if (!sm)
411 return 0;
413 sval = sval_type_min(estate_type(sm->state));
414 FOR_EACH_PTR(sm->possible, tmp) {
415 sval_t new_min;
417 new_min = estate_min(tmp->state);
418 if (sval_cmp(new_min, sval) > 0)
419 sval = new_min;
420 } END_FOR_EACH_PTR(tmp);
422 if (sval_is_min(sval))
423 return 0;
425 *max = sval_cast(get_type(expr), sval);
426 return 1;
429 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
431 struct sm_state *sm;
432 struct sm_state *tmp;
433 sval_t sval;
435 if (get_implied_min(expr, min))
436 return 1;
438 sm = get_sm_state_expr(SMATCH_EXTRA, expr);
439 if (!sm)
440 return 0;
442 sval = sval_type_max(estate_type(sm->state));
443 FOR_EACH_PTR(sm->possible, tmp) {
444 sval_t new_max;
446 new_max = estate_max(tmp->state);
447 if (sval_cmp(new_max, sval) < 0)
448 sval = new_max;
449 } END_FOR_EACH_PTR(tmp);
451 if (sval_is_max(sval))
452 return 0;
453 *min = sval_cast(get_type(expr), sval);
454 return 1;
457 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied)
459 sval_t ret;
461 ret = sval_blank(expr);
463 switch (implied) {
464 case IMPLIED:
465 case IMPLIED_MAX:
466 case IMPLIED_MIN:
467 case HARD_MAX:
468 if (!get_implied_value_helper(expr, &ret, implied))
469 *undefined = 1;
470 break;
471 case ABSOLUTE_MIN:
472 if (!get_absolute_min_helper(expr, &ret))
473 *undefined = 1;
474 break;
475 case ABSOLUTE_MAX:
476 if (!get_absolute_max_helper(expr, &ret))
477 *undefined = 1;
478 break;
479 case FUZZYMAX:
480 if (!get_fuzzy_max_helper(expr, &ret))
481 *undefined = 1;
482 break;
483 case FUZZYMIN:
484 if (!get_fuzzy_min_helper(expr, &ret))
485 *undefined = 1;
486 break;
487 default:
488 *undefined = 1;
490 return ret;
493 static int get_const_value(struct expression *expr, sval_t *sval)
495 struct symbol *sym;
496 sval_t right;
498 if (expr->type != EXPR_SYMBOL || !expr->symbol)
499 return 0;
500 sym = expr->symbol;
501 if (!(sym->ctype.modifiers & MOD_CONST))
502 return 0;
503 if (get_value(sym->initializer, &right)) {
504 *sval = sval_cast(get_type(expr), right);
505 return 1;
507 return 0;
510 static sval_t _get_value(struct expression *expr, int *undefined, int implied)
512 sval_t ret;
514 if (!expr) {
515 *undefined = 1;
516 return bogus;
518 if (*undefined)
519 return bogus;
521 expr = strip_parens(expr);
523 switch (expr->type) {
524 case EXPR_VALUE:
525 ret = sval_from_val(expr, expr->value);
526 break;
527 case EXPR_PREOP:
528 ret = handle_preop(expr, undefined, implied);
529 break;
530 case EXPR_POSTOP:
531 ret = _get_value(expr->unop, undefined, implied);
532 break;
533 case EXPR_CAST:
534 case EXPR_FORCE_CAST:
535 case EXPR_IMPLIED_CAST:
536 ret = _get_value(expr->cast_expression, undefined, implied);
537 ret = sval_cast(get_type(expr), ret);
538 break;
539 case EXPR_BINOP:
540 ret = handle_binop(expr, undefined, implied);
541 break;
542 case EXPR_COMPARE:
543 ret = handle_comparison(expr, undefined, implied);
544 break;
545 case EXPR_LOGICAL:
546 ret = handle_logical(expr, undefined, implied);
547 break;
548 case EXPR_PTRSIZEOF:
549 case EXPR_SIZEOF:
550 ret = sval_blank(expr);
551 ret.value = get_expression_value_nomod(expr);
552 break;
553 case EXPR_SYMBOL:
554 if (get_const_value(expr, &ret)) {
555 break;
557 ret = _get_implied_value(expr, undefined, implied);
558 break;
559 case EXPR_SELECT:
560 case EXPR_CONDITIONAL:
561 ret = handle_conditional(expr, undefined, implied);
562 break;
563 default:
564 ret = _get_implied_value(expr, undefined, implied);
566 if (*undefined)
567 return bogus;
568 return ret;
571 /* returns 1 if it can get a value literal or else returns 0 */
572 int get_value(struct expression *expr, sval_t *sval)
574 int undefined = 0;
575 sval_t ret;
577 ret = _get_value(expr, &undefined, NOTIMPLIED);
578 if (undefined)
579 return 0;
580 *sval = ret;
581 return 1;
584 int get_implied_value(struct expression *expr, sval_t *sval)
586 int undefined = 0;
587 sval_t ret;
589 ret = _get_value(expr, &undefined, IMPLIED);
590 if (undefined)
591 return 0;
592 *sval = ret;
593 return 1;
596 int get_implied_min(struct expression *expr, sval_t *sval)
598 int undefined = 0;
599 sval_t ret;
601 ret = _get_value(expr, &undefined, IMPLIED_MIN);
602 if (undefined)
603 return 0;
604 *sval = ret;
605 return 1;
608 int get_implied_max(struct expression *expr, sval_t *sval)
610 int undefined = 0;
611 sval_t ret;
613 ret = _get_value(expr, &undefined, IMPLIED_MAX);
614 if (undefined)
615 return 0;
616 *sval = ret;
617 return 1;
620 int get_hard_max(struct expression *expr, sval_t *sval)
622 int undefined = 0;
623 sval_t ret;
625 ret = _get_value(expr, &undefined, HARD_MAX);
626 if (undefined)
627 return 0;
628 *sval = ret;
629 return 1;
632 int get_fuzzy_min(struct expression *expr, sval_t *sval)
634 int undefined = 0;
635 sval_t ret;
637 ret = _get_value(expr, &undefined, FUZZYMIN);
638 if (undefined)
639 return 0;
640 *sval = ret;
641 return 1;
644 int get_fuzzy_max(struct expression *expr, sval_t *sval)
646 int undefined = 0;
647 sval_t ret;
649 ret = _get_value(expr, &undefined, FUZZYMAX);
650 if (undefined)
651 return 0;
652 *sval = ret;
653 return 1;
656 int get_absolute_min(struct expression *expr, sval_t *sval)
658 int undefined = 0;
659 struct symbol *type;
661 type = get_type(expr);
662 if (!type)
663 type = &llong_ctype; // FIXME: this is wrong but places assume get type can't fail.
664 *sval = _get_value(expr, &undefined, ABSOLUTE_MIN);
665 if (undefined) {
666 *sval = sval_type_min(type);
667 return 1;
670 if (sval_cmp(*sval, sval_type_min(type)) < 0)
671 *sval = sval_type_min(type);
672 return 1;
675 int get_absolute_max(struct expression *expr, sval_t *sval)
677 int undefined = 0;
678 struct symbol *type;
680 type = get_type(expr);
681 if (!type)
682 type = &llong_ctype;
683 *sval = _get_value(expr, &undefined, ABSOLUTE_MAX);
684 if (undefined) {
685 *sval = sval_type_max(type);
686 return 1;
689 if (sval_cmp(sval_type_max(type), *sval) < 0)
690 *sval = sval_type_max(type);
691 return 1;
694 int known_condition_true(struct expression *expr)
696 sval_t tmp;
698 if (!expr)
699 return 0;
701 if (get_value(expr, &tmp) && tmp.value)
702 return 1;
704 return 0;
707 int known_condition_false(struct expression *expr)
709 if (!expr)
710 return 0;
712 if (is_zero(expr))
713 return 1;
715 if (expr->type == EXPR_CALL) {
716 if (sym_name_is("__builtin_constant_p", expr->fn))
717 return 1;
719 return 0;
722 int implied_condition_true(struct expression *expr)
724 sval_t tmp;
726 if (!expr)
727 return 0;
729 if (known_condition_true(expr))
730 return 1;
731 if (get_implied_value(expr, &tmp) && tmp.value)
732 return 1;
734 if (expr->type == EXPR_POSTOP)
735 return implied_condition_true(expr->unop);
737 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
738 return implied_not_equal(expr->unop, 1);
739 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
740 return implied_not_equal(expr->unop, -1);
742 expr = strip_expr(expr);
743 switch (expr->type) {
744 case EXPR_COMPARE:
745 if (do_comparison(expr) == 1)
746 return 1;
747 break;
748 case EXPR_PREOP:
749 if (expr->op == '!') {
750 if (implied_condition_false(expr->unop))
751 return 1;
752 break;
754 break;
755 default:
756 if (implied_not_equal(expr, 0) == 1)
757 return 1;
758 break;
760 return 0;
763 int implied_condition_false(struct expression *expr)
765 struct expression *tmp;
766 sval_t sval;
768 if (!expr)
769 return 0;
771 if (known_condition_false(expr))
772 return 1;
774 switch (expr->type) {
775 case EXPR_COMPARE:
776 if (do_comparison(expr) == 2)
777 return 1;
778 case EXPR_PREOP:
779 if (expr->op == '!') {
780 if (implied_condition_true(expr->unop))
781 return 1;
782 break;
784 tmp = strip_expr(expr);
785 if (tmp != expr)
786 return implied_condition_false(tmp);
787 break;
788 default:
789 if (get_implied_value(expr, &sval) && sval.value == 0)
790 return 1;
791 break;
793 return 0;