4 * Copyright (C) 2010 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
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
);
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
};
29 #define ABSOLUTE_MIN 6
30 #define ABSOLUTE_MAX 7
32 static int opposite_implied(int implied
)
34 if (implied
== IMPLIED_MIN
)
36 if (implied
== IMPLIED_MAX
)
38 if (implied
== ABSOLUTE_MIN
)
40 if (implied
== ABSOLUTE_MAX
)
45 static int last_stmt_sval(struct statement
*stmt
, sval_t
*sval
)
47 struct expression
*expr
;
52 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
53 if (stmt
->type
!= STMT_EXPRESSION
)
55 expr
= stmt
->expression
;
56 if (!get_value_sval(expr
, sval
))
61 static sval_t
handle_expression_statement(struct expression
*expr
, int *undefined
, int implied
)
63 struct statement
*stmt
;
66 stmt
= get_expression_statement(expr
);
67 if (!last_stmt_sval(stmt
, &ret
)) {
75 static sval_t
handle_ampersand(int *undefined
, int implied
)
79 ret
.type
= &ptr_ctype
;
82 if (implied
== IMPLIED_MIN
|| implied
== FUZZYMIN
|| implied
== ABSOLUTE_MIN
)
83 return valid_ptr_min_sval
;
84 if (implied
== IMPLIED_MAX
|| implied
== FUZZYMAX
|| implied
== ABSOLUTE_MAX
)
85 return valid_ptr_max_sval
;
91 static sval_t
handle_preop(struct expression
*expr
, int *undefined
, int implied
)
97 ret
= handle_ampersand(undefined
, implied
);
100 ret
= _get_value(expr
->unop
, undefined
, implied
);
101 ret
= sval_preop(ret
, '!');
104 ret
= _get_value(expr
->unop
, undefined
, implied
);
105 ret
= sval_preop(ret
, '~');
106 ret
= sval_cast(ret
, get_type(expr
->unop
));
109 ret
= _get_value(expr
->unop
, undefined
, implied
);
110 ret
= sval_preop(ret
, '-');
113 ret
= _get_implied_value(expr
, undefined
, implied
);
116 ret
= handle_expression_statement(expr
, undefined
, implied
);
120 ret
= sval_blank(expr
);
122 ret
= sval_cast(ret
, get_type(expr
));
126 static sval_t
handle_divide(struct expression
*expr
, int *undefined
, int implied
)
130 left
= _get_value(expr
->left
, undefined
, implied
);
131 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
133 if (right
.value
== 0) {
138 return sval_binop(left
, '/', right
);
141 static sval_t
handle_subtract(struct expression
*expr
, int *undefined
, int implied
)
145 left
= _get_value(expr
->left
, undefined
, implied
);
146 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
148 return sval_binop(left
, '-', right
);
151 static sval_t
handle_binop(struct expression
*expr
, int *undefined
, int implied
)
154 sval_t ret
= {.type
= &int_ctype
, .value
= 123456};
159 left
= _get_value(expr
->left
, &local_undef
, implied
);
161 if (implied
== ABSOLUTE_MIN
) {
162 ret
= sval_blank(expr
->left
);
166 if (implied
!= ABSOLUTE_MAX
)
168 if (!get_absolute_max_sval(expr
->left
, &left
))
171 right
= _get_value(expr
->right
, undefined
, implied
);
172 if (right
.value
== 0)
175 ret
= sval_binop(left
, '%', right
);
179 left
= _get_value(expr
->left
, &local_undef
, implied
);
181 if (implied
== ABSOLUTE_MIN
) {
182 ret
= sval_blank(expr
->left
);
186 if (implied
!= ABSOLUTE_MAX
)
188 if (!get_absolute_max_sval(expr
->left
, &left
))
191 right
= _get_value(expr
->right
, undefined
, implied
);
192 return sval_binop(left
, '&', right
);
194 case SPECIAL_RIGHTSHIFT
:
195 left
= _get_value(expr
->left
, &local_undef
, implied
);
197 if (implied
== ABSOLUTE_MIN
) {
198 ret
= sval_blank(expr
->left
);
202 if (implied
!= ABSOLUTE_MAX
)
204 if (!get_absolute_max_sval(expr
->left
, &left
))
207 right
= _get_value(expr
->right
, undefined
, implied
);
208 return sval_binop(left
, SPECIAL_RIGHTSHIFT
, right
);
211 left
= _get_value(expr
->left
, undefined
, implied
);
212 right
= _get_value(expr
->right
, undefined
, implied
);
216 return handle_divide(expr
, undefined
, implied
);
218 if (right
.value
== 0)
221 ret
= sval_binop(left
, '%', right
);
224 ret
= handle_subtract(expr
, undefined
, implied
);
227 ret
= sval_binop(left
, expr
->op
, right
);
232 static int do_comparison(struct expression
*expr
)
234 struct range_list_sval
*left_ranges
= NULL
;
235 struct range_list_sval
*right_ranges
= NULL
;
236 int poss_true
, poss_false
;
238 get_implied_range_list_sval(expr
->left
, &left_ranges
);
239 get_implied_range_list_sval(expr
->right
, &right_ranges
);
241 poss_true
= possibly_true_range_lists_sval(left_ranges
, expr
->op
, right_ranges
);
242 poss_false
= possibly_false_range_lists_sval(left_ranges
, expr
->op
, right_ranges
);
244 free_range_list_sval(&left_ranges
);
245 free_range_list_sval(&right_ranges
);
247 if (!poss_true
&& !poss_false
)
249 if (poss_true
&& !poss_false
)
251 if (!poss_true
&& poss_false
)
256 static sval_t
handle_comparison(struct expression
*expr
, int *undefined
, int implied
)
261 if (get_value_sval(expr
->left
, &left
) && get_value_sval(expr
->right
, &right
)) {
262 struct data_range_sval tmp_left
, tmp_right
;
266 tmp_right
.min
= right
;
267 tmp_right
.max
= right
;
268 if (true_comparison_range_sval(&tmp_left
, expr
->op
, &tmp_right
))
273 if (implied
== NOTIMPLIED
) {
278 res
= do_comparison(expr
);
284 if (implied
== IMPLIED_MIN
|| implied
== FUZZYMIN
|| implied
== ABSOLUTE_MIN
)
286 if (implied
== IMPLIED_MAX
|| implied
== FUZZYMAX
|| implied
== ABSOLUTE_MAX
)
293 static sval_t
handle_logical(struct expression
*expr
, int *undefined
, int implied
)
297 if ((implied
== NOTIMPLIED
&& get_value_sval(expr
->left
, &left
) &&
298 get_value_sval(expr
->right
, &right
)) ||
299 (implied
!= NOTIMPLIED
&& get_implied_value_sval(expr
->left
, &left
) &&
300 get_implied_value_sval(expr
->right
, &right
))) {
302 case SPECIAL_LOGICAL_OR
:
303 if (left
.value
|| right
.value
)
306 case SPECIAL_LOGICAL_AND
:
307 if (left
.value
&& right
.value
)
316 if (implied
== IMPLIED_MIN
|| implied
== FUZZYMIN
|| implied
== ABSOLUTE_MIN
)
318 if (implied
== IMPLIED_MAX
|| implied
== FUZZYMAX
|| implied
== ABSOLUTE_MAX
)
325 static sval_t
handle_conditional(struct expression
*expr
, int *undefined
, int implied
)
327 if (known_condition_true(expr
->conditional
))
328 return _get_value(expr
->cond_true
, undefined
, implied
);
329 if (known_condition_false(expr
->conditional
))
330 return _get_value(expr
->cond_false
, undefined
, implied
);
332 if (implied
== NOTIMPLIED
) {
337 if (implied_condition_true(expr
->conditional
))
338 return _get_value(expr
->cond_true
, undefined
, implied
);
339 if (implied_condition_false(expr
->conditional
))
340 return _get_value(expr
->cond_false
, undefined
, implied
);
346 static int get_implied_value_helper(struct expression
*expr
, sval_t
*sval
, int implied
)
348 struct smatch_state
*state
;
352 /* fixme: this should return the casted value */
354 expr
= strip_expr(expr
);
356 if (get_value_sval(expr
, sval
))
359 name
= get_variable_from_expr(expr
, &sym
);
362 *sval
= sval_blank(expr
);
363 state
= get_state(SMATCH_EXTRA
, name
, sym
);
365 if (!state
|| !state
->data
)
367 if (implied
== IMPLIED
) {
368 if (estate_get_single_value_sval(state
, sval
))
372 if (implied
== IMPLIED_MAX
|| implied
== ABSOLUTE_MAX
) {
373 *sval
= estate_max_sval(state
);
374 if (sval_is_max(*sval
)) /* this means just guessing. fixme. not really */
378 *sval
= estate_min_sval(state
);
379 if (sval_is_min(*sval
)) /* fixme */
384 static int is_some_kind_of_max(sval_t sval
)
386 switch (sval
.uvalue
) {
399 static int get_fuzzy_max_helper(struct expression
*expr
, sval_t
*max
)
402 struct sm_state
*tmp
;
405 if (get_implied_max_sval(expr
, &sval
) && !is_some_kind_of_max(sval
)) {
410 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
414 sval
= sval_type_min(estate_type(sm
->state
));
415 FOR_EACH_PTR(sm
->possible
, tmp
) {
418 new_min
= estate_min_sval(tmp
->state
);
419 if (sval_cmp(new_min
, sval
) > 0)
421 } END_FOR_EACH_PTR(tmp
);
423 if (sval_is_min(sval
))
426 *max
= sval_cast(sval
, get_type(expr
));
430 static int get_fuzzy_min_helper(struct expression
*expr
, sval_t
*min
)
433 struct sm_state
*tmp
;
436 if (get_implied_min_sval(expr
, min
))
439 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
443 sval
= sval_type_max(estate_type(sm
->state
));
444 FOR_EACH_PTR(sm
->possible
, tmp
) {
447 new_max
= estate_max_sval(tmp
->state
);
448 if (sval_cmp(new_max
, sval
) < 0)
450 } END_FOR_EACH_PTR(tmp
);
452 if (sval_is_max(sval
))
454 *min
= sval_cast(sval
, get_type(expr
));
458 static sval_t
_get_implied_value(struct expression
*expr
, int *undefined
, int implied
)
462 ret
= sval_blank(expr
);
468 if (!get_implied_value_helper(expr
, &ret
, implied
))
472 if (!get_absolute_min_helper(expr
, &ret
))
476 if (!get_absolute_max_helper(expr
, &ret
))
480 if (!get_fuzzy_max_helper(expr
, &ret
))
484 if (!get_fuzzy_min_helper(expr
, &ret
))
493 static int get_const_value(struct expression
*expr
, sval_t
*sval
)
498 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
)
501 if (!(sym
->ctype
.modifiers
& MOD_CONST
))
503 if (get_value_sval(sym
->initializer
, &right
)) {
504 *sval
= sval_cast(right
, get_type(expr
));
510 static sval_t
_get_value(struct expression
*expr
, int *undefined
, int implied
)
521 expr
= strip_parens(expr
);
523 switch (expr
->type
) {
525 tmp_ret
= sval_from_val(expr
, expr
->value
);
528 tmp_ret
= handle_preop(expr
, undefined
, implied
);
531 tmp_ret
= _get_value(expr
->unop
, undefined
, implied
);
534 case EXPR_FORCE_CAST
:
535 case EXPR_IMPLIED_CAST
:
536 tmp_ret
= _get_value(expr
->cast_expression
, undefined
, implied
);
537 tmp_ret
= sval_cast(tmp_ret
, get_type(expr
));
540 tmp_ret
= handle_binop(expr
, undefined
, implied
);
543 tmp_ret
= handle_comparison(expr
, undefined
, implied
);
546 tmp_ret
= handle_logical(expr
, undefined
, implied
);
550 tmp_ret
= sval_blank(expr
);
551 tmp_ret
.value
= get_expression_value_nomod(expr
);
554 if (get_const_value(expr
, &tmp_ret
)) {
557 tmp_ret
= _get_implied_value(expr
, undefined
, implied
);
560 case EXPR_CONDITIONAL
:
561 tmp_ret
= handle_conditional(expr
, undefined
, implied
);
564 tmp_ret
= _get_implied_value(expr
, undefined
, implied
);
571 /* returns 1 if it can get a value literal or else returns 0 */
572 int get_value_sval(struct expression
*expr
, sval_t
*sval
)
577 ret
= _get_value(expr
, &undefined
, NOTIMPLIED
);
584 int get_implied_value_sval(struct expression
*expr
, sval_t
*sval
)
589 ret
= _get_value(expr
, &undefined
, IMPLIED
);
596 int get_implied_min_sval(struct expression
*expr
, sval_t
*sval
)
601 ret
= _get_value(expr
, &undefined
, IMPLIED_MIN
);
608 int get_implied_max_sval(struct expression
*expr
, sval_t
*sval
)
613 ret
= _get_value(expr
, &undefined
, IMPLIED_MAX
);
620 int get_fuzzy_min_sval(struct expression
*expr
, sval_t
*sval
)
625 ret
= _get_value(expr
, &undefined
, FUZZYMIN
);
632 int get_fuzzy_max_sval(struct expression
*expr
, sval_t
*sval
)
637 ret
= _get_value(expr
, &undefined
, FUZZYMAX
);
644 int get_absolute_min_sval(struct expression
*expr
, sval_t
*sval
)
649 type
= get_type(expr
);
650 *sval
= _get_value(expr
, &undefined
, ABSOLUTE_MIN
);
652 *sval
= sval_type_min(type
);
656 if (sval_cmp(*sval
, sval_type_min(type
)) < 0)
657 *sval
= sval_type_min(type
);
661 int get_absolute_max_sval(struct expression
*expr
, sval_t
*sval
)
666 type
= get_type(expr
);
667 *sval
= _get_value(expr
, &undefined
, ABSOLUTE_MAX
);
669 *sval
= sval_type_max(type
);
673 if (sval_cmp(sval_type_max(type
), *sval
) < 0)
674 *sval
= sval_type_max(type
);
678 int known_condition_true(struct expression
*expr
)
685 if (get_value_sval(expr
, &tmp
) && tmp
.value
)
691 int known_condition_false(struct expression
*expr
)
699 if (expr
->type
== EXPR_CALL
) {
700 if (sym_name_is("__builtin_constant_p", expr
->fn
))
706 int implied_condition_true(struct expression
*expr
)
713 if (known_condition_true(expr
))
715 if (get_implied_value_sval(expr
, &tmp
) && tmp
.value
)
718 if (expr
->type
== EXPR_POSTOP
)
719 return implied_condition_true(expr
->unop
);
721 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_DECREMENT
)
722 return implied_not_equal(expr
->unop
, 1);
723 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_INCREMENT
)
724 return implied_not_equal(expr
->unop
, -1);
726 expr
= strip_expr(expr
);
727 switch (expr
->type
) {
729 if (do_comparison(expr
) == 1)
733 if (expr
->op
== '!') {
734 if (implied_condition_false(expr
->unop
))
740 if (implied_not_equal(expr
, 0) == 1)
747 int implied_condition_false(struct expression
*expr
)
749 struct expression
*tmp
;
755 if (known_condition_false(expr
))
758 switch (expr
->type
) {
760 if (do_comparison(expr
) == 2)
763 if (expr
->op
== '!') {
764 if (implied_condition_true(expr
->unop
))
768 tmp
= strip_expr(expr
);
770 return implied_condition_false(tmp
);
773 if (get_implied_value_sval(expr
, &sval
) && sval
.value
== 0)