4 * Copyright (C) 2010 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
12 #include "smatch_slist.h"
13 #include "smatch_extra.h"
15 static sval_t
_get_value(struct expression
*expr
, int *undefined
, int implied
);
16 static sval_t
_get_implied_value(struct expression
*expr
, int *undefined
, int implied
);
20 static sval_t zero
= {.type
= &int_ctype
, .value
= 0};
21 static sval_t one
= {.type
= &int_ctype
, .value
= 1};
22 static sval_t bogus
= {.type
= &int_ctype
, .value
= BOGUS
};
36 static int opposite_implied(int implied
)
38 if (implied
== IMPLIED_MIN
)
40 if (implied
== IMPLIED_MAX
)
42 if (implied
== FUZZY_MIN
)
44 if (implied
== FUZZY_MAX
)
46 if (implied
== ABSOLUTE_MIN
)
48 if (implied
== ABSOLUTE_MAX
)
54 static int last_stmt_sval(struct statement
*stmt
, sval_t
*sval
)
56 struct expression
*expr
;
61 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
62 if (stmt
->type
!= STMT_EXPRESSION
)
64 expr
= stmt
->expression
;
65 if (!get_value(expr
, sval
))
70 static sval_t
handle_expression_statement(struct expression
*expr
, int *undefined
, int implied
)
72 struct statement
*stmt
;
75 stmt
= get_expression_statement(expr
);
76 if (!last_stmt_sval(stmt
, &ret
)) {
84 static sval_t
handle_ampersand(int *undefined
, int implied
)
88 ret
.type
= &ptr_ctype
;
91 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
)
92 return valid_ptr_min_sval
;
93 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
)
94 return valid_ptr_max_sval
;
100 static sval_t
handle_negate(struct expression
*expr
, int *undefined
, int implied
)
104 ret
= sval_blank(expr
->unop
);
106 if (known_condition_true(expr
->unop
)) {
111 if (implied
== NOTIMPLIED
) {
116 if (implied_condition_true(expr
->unop
)) {
120 if (implied_condition_false(expr
->unop
)) {
124 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
) {
128 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
) {
136 static sval_t
handle_preop(struct expression
*expr
, int *undefined
, int implied
)
142 ret
= handle_ampersand(undefined
, implied
);
145 ret
= handle_negate(expr
, undefined
, implied
);
148 ret
= _get_value(expr
->unop
, undefined
, implied
);
149 ret
= sval_preop(ret
, '~');
150 ret
= sval_cast(get_type(expr
->unop
), ret
);
153 ret
= _get_value(expr
->unop
, undefined
, implied
);
154 ret
= sval_preop(ret
, '-');
157 ret
= _get_implied_value(expr
, undefined
, implied
);
160 ret
= handle_expression_statement(expr
, undefined
, implied
);
164 ret
= sval_blank(expr
);
166 ret
= sval_cast(get_type(expr
), ret
);
170 static sval_t
handle_divide(struct expression
*expr
, int *undefined
, int implied
)
174 left
= _get_value(expr
->left
, undefined
, implied
);
175 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
177 if (right
.value
== 0) {
182 return sval_binop(left
, '/', right
);
185 static sval_t
handle_subtract(struct expression
*expr
, int *undefined
, int implied
)
188 sval_t left
, right
, ret
;
189 int left_undefined
= 0;
190 int right_undefined
= 0;
191 int known_but_negative
= 0;
194 left
= _get_value(expr
->left
, &left_undefined
, implied
);
195 right
= _get_value(expr
->right
, &right_undefined
, opposite_implied(implied
));
197 if (!left_undefined
&& !right_undefined
) {
198 ret
= sval_binop(left
, '-', right
);
199 if (sval_is_negative(ret
))
200 known_but_negative
= 1;
202 return ret
; /* best case scenario */
205 comparison
= get_comparison(expr
->left
, expr
->right
);
209 type
= get_type(expr
);
211 switch (comparison
) {
213 case SPECIAL_UNSIGNED_GT
:
218 return sval_type_val(type
, 1);
222 return _get_value(expr
->left
, undefined
, implied
);
226 case SPECIAL_UNSIGNED_GTE
:
231 return sval_type_val(type
, 0);
235 return _get_value(expr
->left
, undefined
, implied
);
240 if (known_but_negative
)
248 static sval_t
handle_mod(struct expression
*expr
, int *undefined
, int implied
)
252 /* if we can't figure out the right side it's probably hopeless */
253 right
= _get_value(expr
->right
, undefined
, implied
);
254 if (*undefined
|| right
.value
== 0)
257 left
= _get_value(expr
->left
, undefined
, implied
);
259 return sval_binop(left
, '%', right
);
269 return sval_type_val(get_type(expr
->left
), 0);
274 right
= sval_cast(get_type(expr
), right
);
281 static sval_t
handle_binop(struct expression
*expr
, int *undefined
, int implied
)
285 sval_t ret
= {.type
= &int_ctype
, .value
= 123456};
290 return handle_mod(expr
, undefined
, implied
);
292 left
= _get_value(expr
->left
, &local_undef
, implied
);
294 if (implied
== IMPLIED_MIN
|| implied
== ABSOLUTE_MIN
) {
295 ret
= sval_blank(expr
->left
);
299 if (implied
!= IMPLIED_MAX
&& implied
!= ABSOLUTE_MAX
)
301 if (!get_absolute_max(expr
->left
, &left
))
304 right
= _get_value(expr
->right
, undefined
, implied
);
307 return sval_binop(left
, '&', right
);
309 case SPECIAL_RIGHTSHIFT
:
310 left
= _get_value(expr
->left
, &local_undef
, implied
);
312 if (implied
== IMPLIED_MIN
|| implied
== ABSOLUTE_MIN
) {
313 ret
= sval_blank(expr
->left
);
317 if (implied
!= IMPLIED_MAX
&& implied
!= ABSOLUTE_MAX
)
319 if (!get_absolute_max(expr
->left
, &left
))
322 right
= _get_value(expr
->right
, undefined
, implied
);
325 return sval_binop(left
, SPECIAL_RIGHTSHIFT
, right
);
327 return handle_subtract(expr
, undefined
, implied
);
330 left
= _get_value(expr
->left
, undefined
, implied
);
331 right
= _get_value(expr
->right
, undefined
, implied
);
336 type
= get_type(expr
);
337 left
= sval_cast(type
, left
);
338 right
= sval_cast(type
, right
);
343 if (sval_binop_overflows(left
, expr
->op
, right
))
344 return sval_type_max(get_type(expr
));
348 if (sval_binop_overflows(left
, expr
->op
, right
)) {
356 return handle_divide(expr
, undefined
, implied
);
358 if (right
.value
== 0) {
362 return sval_binop(left
, '%', right
);
365 ret
= sval_binop(left
, expr
->op
, right
);
370 static int do_comparison(struct expression
*expr
)
372 struct range_list
*left_ranges
= NULL
;
373 struct range_list
*right_ranges
= NULL
;
374 int poss_true
, poss_false
;
376 get_implied_rl(expr
->left
, &left_ranges
);
377 get_implied_rl(expr
->right
, &right_ranges
);
379 poss_true
= possibly_true_rl(left_ranges
, expr
->op
, right_ranges
);
380 poss_false
= possibly_false_rl(left_ranges
, expr
->op
, right_ranges
);
382 free_rl(&left_ranges
);
383 free_rl(&right_ranges
);
385 if (!poss_true
&& !poss_false
)
387 if (poss_true
&& !poss_false
)
389 if (!poss_true
&& poss_false
)
394 static sval_t
handle_comparison(struct expression
*expr
, int *undefined
, int implied
)
399 if (get_value(expr
->left
, &left
) && get_value(expr
->right
, &right
)) {
400 struct data_range tmp_left
, tmp_right
;
404 tmp_right
.min
= right
;
405 tmp_right
.max
= right
;
406 if (true_comparison_range(&tmp_left
, expr
->op
, &tmp_right
))
411 if (implied
== NOTIMPLIED
) {
416 res
= do_comparison(expr
);
422 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
)
424 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
)
431 static sval_t
handle_logical(struct expression
*expr
, int *undefined
, int implied
)
437 if (implied
== NOTIMPLIED
) {
438 if (get_value(expr
->left
, &left
))
440 if (get_value(expr
->right
, &right
))
443 if (get_implied_value(expr
->left
, &left
))
445 if (get_implied_value(expr
->right
, &right
))
450 case SPECIAL_LOGICAL_OR
:
451 if (left_known
&& left
.value
)
453 if (right_known
&& right
.value
)
455 if (left_known
&& right_known
)
458 case SPECIAL_LOGICAL_AND
:
459 if (left_known
&& right_known
) {
460 if (left
.value
&& right
.value
)
470 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
)
472 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
)
479 static sval_t
handle_conditional(struct expression
*expr
, int *undefined
, int implied
)
481 if (known_condition_true(expr
->conditional
))
482 return _get_value(expr
->cond_true
, undefined
, implied
);
483 if (known_condition_false(expr
->conditional
))
484 return _get_value(expr
->cond_false
, undefined
, implied
);
486 if (implied
== NOTIMPLIED
) {
491 if (implied_condition_true(expr
->conditional
))
492 return _get_value(expr
->cond_true
, undefined
, implied
);
493 if (implied_condition_false(expr
->conditional
))
494 return _get_value(expr
->cond_false
, undefined
, implied
);
500 static int get_implied_value_helper(struct expression
*expr
, sval_t
*sval
, int implied
)
502 struct smatch_state
*state
;
506 /* fixme: this should return the casted value */
508 expr
= strip_expr(expr
);
510 if (get_value(expr
, sval
))
513 name
= expr_to_var_sym(expr
, &sym
);
516 *sval
= sval_blank(expr
);
517 state
= get_state(SMATCH_EXTRA
, name
, sym
);
519 if (!state
|| !state
->data
)
521 if (implied
== IMPLIED
) {
522 if (estate_get_single_value(state
, sval
))
526 if (implied
== HARD_MAX
) {
527 if (estate_get_hard_max(state
, sval
))
531 if (implied
== IMPLIED_MAX
) {
532 *sval
= estate_max(state
);
533 if (sval_is_max(*sval
)) /* this means just guessing. fixme. not really */
537 *sval
= estate_min(state
);
538 if (sval_is_min(*sval
)) /* fixme */
543 static int get_fuzzy_max_helper(struct expression
*expr
, sval_t
*max
)
546 struct sm_state
*tmp
;
549 if (get_hard_max(expr
, &sval
)) {
554 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
558 sval
= sval_type_min(estate_type(sm
->state
));
559 FOR_EACH_PTR(sm
->possible
, tmp
) {
562 new_min
= estate_min(tmp
->state
);
563 if (sval_cmp(new_min
, sval
) > 0)
565 } END_FOR_EACH_PTR(tmp
);
567 if (sval_is_min(sval
))
569 if (sval
.value
== sval_type_min(sval
.type
).value
+ 1) /* it's common to be on off */
572 *max
= sval_cast(get_type(expr
), sval
);
576 static int get_fuzzy_min_helper(struct expression
*expr
, sval_t
*min
)
579 struct sm_state
*tmp
;
582 if (get_implied_min(expr
, min
))
585 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
589 sval
= sval_type_max(estate_type(sm
->state
));
590 FOR_EACH_PTR(sm
->possible
, tmp
) {
593 new_max
= estate_max(tmp
->state
);
594 if (sval_cmp(new_max
, sval
) < 0)
596 } END_FOR_EACH_PTR(tmp
);
598 if (sval_is_max(sval
))
600 *min
= sval_cast(get_type(expr
), sval
);
604 static sval_t
_get_implied_value(struct expression
*expr
, int *undefined
, int implied
)
608 ret
= sval_blank(expr
);
615 if (!get_implied_value_helper(expr
, &ret
, implied
))
619 if (!get_absolute_min_helper(expr
, &ret
))
623 if (!get_absolute_max_helper(expr
, &ret
))
627 if (!get_fuzzy_max_helper(expr
, &ret
))
631 if (!get_fuzzy_min_helper(expr
, &ret
))
640 static int get_const_value(struct expression
*expr
, sval_t
*sval
)
645 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
)
648 if (!(sym
->ctype
.modifiers
& MOD_CONST
))
650 if (get_value(sym
->initializer
, &right
)) {
651 *sval
= sval_cast(get_type(expr
), right
);
657 static sval_t
handle_sizeof(struct expression
*expr
)
662 ret
= sval_blank(expr
);
663 sym
= expr
->cast_type
;
665 sym
= evaluate_expression(expr
->cast_expression
);
667 * Expressions of restricted types will possibly get
668 * promoted - check that here
670 if (is_restricted_type(sym
)) {
671 if (sym
->bit_size
< bits_in_int
)
673 } else if (is_fouled_type(sym
)) {
677 examine_symbol_type(sym
);
679 ret
.type
= size_t_ctype
;
680 if (sym
->bit_size
<= 0) /* sizeof(void) */
683 ret
.value
= bits_to_bytes(sym
->bit_size
);
688 static sval_t
_get_value(struct expression
*expr
, int *undefined
, int implied
)
699 expr
= strip_parens(expr
);
701 switch (expr
->type
) {
703 ret
= sval_from_val(expr
, expr
->value
);
706 ret
= handle_preop(expr
, undefined
, implied
);
709 ret
= _get_value(expr
->unop
, undefined
, implied
);
712 case EXPR_FORCE_CAST
:
713 case EXPR_IMPLIED_CAST
:
714 ret
= _get_value(expr
->cast_expression
, undefined
, implied
);
715 ret
= sval_cast(get_type(expr
), ret
);
718 ret
= handle_binop(expr
, undefined
, implied
);
721 ret
= handle_comparison(expr
, undefined
, implied
);
724 ret
= handle_logical(expr
, undefined
, implied
);
728 ret
= handle_sizeof(expr
);
731 if (get_const_value(expr
, &ret
)) {
734 ret
= _get_implied_value(expr
, undefined
, implied
);
737 case EXPR_CONDITIONAL
:
738 ret
= handle_conditional(expr
, undefined
, implied
);
741 ret
= _get_implied_value(expr
, undefined
, implied
);
748 /* returns 1 if it can get a value literal or else returns 0 */
749 int get_value(struct expression
*expr
, sval_t
*sval
)
754 ret
= _get_value(expr
, &undefined
, NOTIMPLIED
);
761 int get_implied_value(struct expression
*expr
, sval_t
*sval
)
766 ret
= _get_value(expr
, &undefined
, IMPLIED
);
773 int get_implied_min(struct expression
*expr
, sval_t
*sval
)
778 ret
= _get_value(expr
, &undefined
, IMPLIED_MIN
);
785 int get_implied_max(struct expression
*expr
, sval_t
*sval
)
790 ret
= _get_value(expr
, &undefined
, IMPLIED_MAX
);
797 int get_implied_rl(struct expression
*expr
, struct range_list
**rl
)
800 struct smatch_state
*state
;
807 expr
= strip_parens(expr
);
811 state
= get_state_expr(SMATCH_EXTRA
, expr
);
813 *rl
= clone_rl(estate_rl(state
));
817 if (expr
->type
== EXPR_CALL
) {
818 if (get_implied_return(expr
, rl
))
820 *rl
= db_return_vals(expr
);
826 if (get_implied_value(expr
, &sval
)) {
827 add_range(rl
, sval
, sval
);
831 min_known
= get_implied_min(expr
, &min
);
832 max_known
= get_implied_max(expr
, &max
);
833 if (!min_known
&& !max_known
)
836 get_absolute_min(expr
, &min
);
838 get_absolute_max(expr
, &max
);
840 *rl
= alloc_rl(min
, max
);
844 int get_hard_max(struct expression
*expr
, sval_t
*sval
)
849 ret
= _get_value(expr
, &undefined
, HARD_MAX
);
856 int get_fuzzy_min(struct expression
*expr
, sval_t
*sval
)
861 ret
= _get_value(expr
, &undefined
, FUZZY_MIN
);
868 int get_fuzzy_max(struct expression
*expr
, sval_t
*sval
)
873 ret
= _get_value(expr
, &undefined
, FUZZY_MAX
);
880 int get_absolute_min(struct expression
*expr
, sval_t
*sval
)
885 type
= get_type(expr
);
887 type
= &llong_ctype
; // FIXME: this is wrong but places assume get type can't fail.
888 *sval
= _get_value(expr
, &undefined
, ABSOLUTE_MIN
);
890 *sval
= sval_type_min(type
);
894 if (sval_cmp(*sval
, sval_type_min(type
)) < 0)
895 *sval
= sval_type_min(type
);
899 int get_absolute_max(struct expression
*expr
, sval_t
*sval
)
904 type
= get_type(expr
);
907 *sval
= _get_value(expr
, &undefined
, ABSOLUTE_MAX
);
909 *sval
= sval_type_max(type
);
913 if (sval_cmp(sval_type_max(type
), *sval
) < 0)
914 *sval
= sval_type_max(type
);
918 int known_condition_true(struct expression
*expr
)
925 if (get_value(expr
, &tmp
) && tmp
.value
)
931 int known_condition_false(struct expression
*expr
)
939 if (expr
->type
== EXPR_CALL
) {
940 if (sym_name_is("__builtin_constant_p", expr
->fn
))
946 int implied_condition_true(struct expression
*expr
)
953 if (known_condition_true(expr
))
955 if (get_implied_value(expr
, &tmp
) && tmp
.value
)
958 if (expr
->type
== EXPR_POSTOP
)
959 return implied_condition_true(expr
->unop
);
961 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_DECREMENT
)
962 return implied_not_equal(expr
->unop
, 1);
963 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_INCREMENT
)
964 return implied_not_equal(expr
->unop
, -1);
966 expr
= strip_expr(expr
);
967 switch (expr
->type
) {
969 if (do_comparison(expr
) == 1)
973 if (expr
->op
== '!') {
974 if (implied_condition_false(expr
->unop
))
980 if (implied_not_equal(expr
, 0) == 1)
987 int implied_condition_false(struct expression
*expr
)
989 struct expression
*tmp
;
995 if (known_condition_false(expr
))
998 switch (expr
->type
) {
1000 if (do_comparison(expr
) == 2)
1003 if (expr
->op
== '!') {
1004 if (implied_condition_true(expr
->unop
))
1008 tmp
= strip_expr(expr
);
1010 return implied_condition_false(tmp
);
1013 if (get_implied_value(expr
, &sval
) && sval
.value
== 0)