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 ret
.value
= valid_ptr_min
;
84 if (implied
== IMPLIED_MAX
|| implied
== FUZZYMAX
|| implied
== ABSOLUTE_MAX
)
85 ret
.value
= valid_ptr_max
;
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
, 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
);
125 static sval_t
handle_divide(struct expression
*expr
, int *undefined
, int implied
)
129 left
= _get_value(expr
->left
, undefined
, implied
);
130 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
132 if (right
.value
== 0)
135 return sval_binop(left
, '/', right
);
138 static sval_t
handle_subtract(struct expression
*expr
, int *undefined
, int implied
)
142 left
= _get_value(expr
->left
, undefined
, implied
);
143 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
145 return sval_binop(left
, '-', right
);
148 static sval_t
handle_binop(struct expression
*expr
, int *undefined
, int implied
)
151 sval_t ret
= {.type
= &int_ctype
, .value
= 123456};
156 left
= _get_value(expr
->left
, &local_undef
, implied
);
158 if (implied
== ABSOLUTE_MIN
) {
159 ret
= sval_blank(expr
->left
);
163 if (implied
!= ABSOLUTE_MAX
)
165 if (!get_absolute_max_sval(expr
->left
, &left
))
168 right
= _get_value(expr
->right
, undefined
, implied
);
169 if (right
.value
== 0)
172 ret
= sval_binop(left
, '%', right
);
176 left
= _get_value(expr
->left
, &local_undef
, implied
);
178 if (implied
== ABSOLUTE_MIN
) {
179 ret
= sval_blank(expr
->left
);
183 if (implied
!= ABSOLUTE_MAX
)
185 if (!get_absolute_max_sval(expr
->left
, &left
))
188 right
= _get_value(expr
->right
, undefined
, implied
);
189 return sval_binop(left
, '&', right
);
191 case SPECIAL_RIGHTSHIFT
:
192 left
= _get_value(expr
->left
, &local_undef
, implied
);
194 if (implied
== ABSOLUTE_MIN
) {
195 ret
= sval_blank(expr
->left
);
199 if (implied
!= ABSOLUTE_MAX
)
201 if (!get_absolute_max_sval(expr
->left
, &left
))
204 right
= _get_value(expr
->right
, undefined
, implied
);
205 return sval_binop(left
, SPECIAL_RIGHTSHIFT
, right
);
208 left
= _get_value(expr
->left
, undefined
, implied
);
209 right
= _get_value(expr
->right
, undefined
, implied
);
213 return handle_divide(expr
, undefined
, implied
);
215 if (right
.value
== 0)
218 ret
= sval_binop(left
, '%', right
);
221 ret
= handle_subtract(expr
, undefined
, implied
);
224 ret
= sval_binop(left
, expr
->op
, right
);
229 static int do_comparison(struct expression
*expr
)
231 struct range_list
*left_ranges
= NULL
;
232 struct range_list
*right_ranges
= NULL
;
233 int poss_true
, poss_false
;
235 get_implied_range_list(expr
->left
, &left_ranges
);
236 get_implied_range_list(expr
->right
, &right_ranges
);
238 poss_true
= possibly_true_range_lists(left_ranges
, expr
->op
, right_ranges
);
239 poss_false
= possibly_false_range_lists(left_ranges
, expr
->op
, right_ranges
);
241 free_range_list(&left_ranges
);
242 free_range_list(&right_ranges
);
244 if (!poss_true
&& !poss_false
)
246 if (poss_true
&& !poss_false
)
248 if (!poss_true
&& poss_false
)
253 static sval_t
handle_comparison(struct expression
*expr
, int *undefined
, int implied
)
258 if (get_value_sval(expr
->left
, &left
) && get_value_sval(expr
->right
, &right
)) {
259 struct data_range_sval tmp_left
, tmp_right
;
263 tmp_right
.min
= right
;
264 tmp_right
.max
= right
;
265 if (true_comparison_range_sval(&tmp_left
, expr
->op
, &tmp_right
))
270 if (implied
== NOTIMPLIED
) {
275 res
= do_comparison(expr
);
281 if (implied
== IMPLIED_MIN
|| implied
== FUZZYMIN
|| implied
== ABSOLUTE_MIN
)
283 if (implied
== IMPLIED_MAX
|| implied
== FUZZYMAX
|| implied
== ABSOLUTE_MAX
)
290 static sval_t
handle_logical(struct expression
*expr
, int *undefined
, int implied
)
294 if ((implied
== NOTIMPLIED
&& get_value_sval(expr
->left
, &left
) &&
295 get_value_sval(expr
->right
, &right
)) ||
296 (implied
!= NOTIMPLIED
&& get_implied_value_sval(expr
->left
, &left
) &&
297 get_implied_value_sval(expr
->right
, &right
))) {
299 case SPECIAL_LOGICAL_OR
:
300 if (left
.value
|| right
.value
)
303 case SPECIAL_LOGICAL_AND
:
304 if (left
.value
&& right
.value
)
313 if (implied
== IMPLIED_MIN
|| implied
== FUZZYMIN
|| implied
== ABSOLUTE_MIN
)
315 if (implied
== IMPLIED_MAX
|| implied
== FUZZYMAX
|| implied
== ABSOLUTE_MAX
)
322 static sval_t
handle_conditional(struct expression
*expr
, int *undefined
, int implied
)
324 if (known_condition_true(expr
->conditional
))
325 return _get_value(expr
->cond_true
, undefined
, implied
);
326 if (known_condition_false(expr
->conditional
))
327 return _get_value(expr
->cond_false
, undefined
, implied
);
329 if (implied
== NOTIMPLIED
) {
334 if (implied_condition_true(expr
->conditional
))
335 return _get_value(expr
->cond_true
, undefined
, implied
);
336 if (implied_condition_false(expr
->conditional
))
337 return _get_value(expr
->cond_false
, undefined
, implied
);
343 static int get_implied_value_helper(struct expression
*expr
, sval_t
*sval
, int implied
)
345 struct smatch_state
*state
;
349 /* fixme: this should return the casted value */
351 expr
= strip_expr(expr
);
353 if (get_value_sval(expr
, sval
))
356 name
= get_variable_from_expr(expr
, &sym
);
359 *sval
= sval_blank(expr
);
360 state
= get_state(SMATCH_EXTRA
, name
, sym
);
362 if (!state
|| !state
->data
)
364 if (implied
== IMPLIED
) {
365 if (estate_get_single_value_sval(state
, sval
))
369 if (implied
== IMPLIED_MAX
|| implied
== ABSOLUTE_MAX
) {
370 *sval
= estate_max_sval(state
);
371 if (sval_is_max(*sval
)) /* this means just guessing. fixme. not really */
375 *sval
= estate_min_sval(state
);
376 if (sval_is_min(*sval
)) /* fixme */
381 static int get_fuzzy_max_helper(struct expression
*expr
, sval_t
*max
)
384 struct sm_state
*tmp
;
387 if (get_implied_max_sval(expr
, max
))
390 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
394 sval
= sval_type_min(&llong_ctype
);
395 FOR_EACH_PTR(sm
->possible
, tmp
) {
398 new_min
= estate_min_sval(tmp
->state
);
399 if (sval_cmp(new_min
, sval
) > 0)
401 } END_FOR_EACH_PTR(tmp
);
403 if (sval_is_min(sval
))
406 *max
= sval_cast(sval
, expr
);
410 static int get_fuzzy_min_helper(struct expression
*expr
, sval_t
*min
)
413 struct sm_state
*tmp
;
416 if (get_implied_min_sval(expr
, min
))
419 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
423 sval
= sval_type_max(&llong_ctype
);
424 FOR_EACH_PTR(sm
->possible
, tmp
) {
427 new_max
= estate_max_sval(tmp
->state
);
428 if (sval_cmp(new_max
, sval
) < 0)
430 } END_FOR_EACH_PTR(tmp
);
432 if (sval_is_max(sval
))
434 *min
= sval_cast(sval
, expr
);
438 static sval_t
_get_implied_value(struct expression
*expr
, int *undefined
, int implied
)
442 ret
= sval_blank(expr
);
448 if (!get_implied_value_helper(expr
, &ret
, implied
))
453 struct smatch_state
*state
;
454 struct data_range
*range
;
456 if (get_implied_value_helper(expr
, &ret
, implied
))
459 state
= get_state_expr(absolute_id
, expr
);
460 if (!state
|| !state
->data
) {
465 if (implied
== ABSOLUTE_MAX
)
466 ret
.value
= range
->max
;
468 ret
.value
= range
->min
;
472 if (!get_fuzzy_max_helper(expr
, &ret
))
476 if (!get_fuzzy_min_helper(expr
, &ret
))
485 static int get_const_value(struct expression
*expr
, sval_t
*sval
)
490 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
)
493 if (!(sym
->ctype
.modifiers
& MOD_CONST
))
495 if (get_value_sval(sym
->initializer
, &right
)) {
496 *sval
= sval_cast(right
, expr
);
502 static sval_t
_get_value(struct expression
*expr
, int *undefined
, int implied
)
513 expr
= strip_parens(expr
);
515 switch (expr
->type
) {
517 tmp_ret
= sval_from_val(expr
, expr
->value
);
520 tmp_ret
= handle_preop(expr
, undefined
, implied
);
523 tmp_ret
= _get_value(expr
->unop
, undefined
, implied
);
526 case EXPR_FORCE_CAST
:
527 case EXPR_IMPLIED_CAST
:
528 tmp_ret
= _get_value(expr
->cast_expression
, undefined
, implied
);
529 tmp_ret
= sval_cast(tmp_ret
, expr
);
532 tmp_ret
= handle_binop(expr
, undefined
, implied
);
535 tmp_ret
= handle_comparison(expr
, undefined
, implied
);
538 tmp_ret
= handle_logical(expr
, undefined
, implied
);
542 tmp_ret
= sval_blank(expr
);
543 tmp_ret
.value
= get_expression_value_nomod(expr
);
546 if (get_const_value(expr
, &tmp_ret
)) {
549 tmp_ret
= _get_implied_value(expr
, undefined
, implied
);
552 case EXPR_CONDITIONAL
:
553 tmp_ret
= handle_conditional(expr
, undefined
, implied
);
556 tmp_ret
= _get_implied_value(expr
, undefined
, implied
);
563 /* returns 1 if it can get a value literal or else returns 0 */
564 int get_value(struct expression
*expr
, long long *val
)
569 tmp_ret
= _get_value(expr
, &undefined
, NOTIMPLIED
);
572 *val
= tmp_ret
.value
;
576 int get_value_sval(struct expression
*expr
, sval_t
*val
)
580 *val
= _get_value(expr
, &undefined
, NOTIMPLIED
);
586 int get_implied_value(struct expression
*expr
, long long *val
)
591 tmp_ret
= _get_value(expr
, &undefined
, IMPLIED
);
592 *val
= tmp_ret
.value
;
596 int get_implied_value_sval(struct expression
*expr
, sval_t
*sval
)
600 *sval
= _get_value(expr
, &undefined
, IMPLIED
);
604 int get_implied_min(struct expression
*expr
, long long *val
)
609 tmp_ret
= _get_value(expr
, &undefined
, IMPLIED_MIN
);
610 *val
= tmp_ret
.value
;
614 int get_implied_min_sval(struct expression
*expr
, sval_t
*sval
)
618 *sval
= _get_value(expr
, &undefined
, IMPLIED_MIN
);
622 int get_implied_max(struct expression
*expr
, long long *val
)
627 tmp_ret
= _get_value(expr
, &undefined
, IMPLIED_MAX
);
628 *val
= tmp_ret
.value
;
632 int get_implied_max_sval(struct expression
*expr
, sval_t
*sval
)
636 *sval
= _get_value(expr
, &undefined
, IMPLIED_MAX
);
640 int get_fuzzy_min(struct expression
*expr
, long long *val
)
645 tmp_ret
= _get_value(expr
, &undefined
, FUZZYMIN
);
646 *val
= tmp_ret
.value
;
650 int get_fuzzy_min_sval(struct expression
*expr
, sval_t
*sval
)
654 *sval
= _get_value(expr
, &undefined
, FUZZYMIN
);
658 int get_fuzzy_max(struct expression
*expr
, long long *val
)
663 tmp_ret
= _get_value(expr
, &undefined
, FUZZYMAX
);
664 *val
= tmp_ret
.value
;
668 int get_fuzzy_max_sval(struct expression
*expr
, sval_t
*sval
)
672 *sval
= _get_value(expr
, &undefined
, FUZZYMAX
);
676 int get_absolute_min(struct expression
*expr
, long long *val
)
680 get_absolute_min_sval(expr
, &tmp_ret
);
681 *val
= tmp_ret
.value
;
685 int get_absolute_min_sval(struct expression
*expr
, sval_t
*sval
)
690 type
= get_type(expr
);
691 *sval
= _get_value(expr
, &undefined
, ABSOLUTE_MIN
);
693 *sval
= sval_type_min(type
);
697 if (sval_cmp(*sval
, sval_type_min(type
)) < 0)
698 *sval
= sval_type_min(type
);
702 int get_absolute_max_sval(struct expression
*expr
, sval_t
*sval
)
706 *sval
= _get_value(expr
, &undefined
, ABSOLUTE_MAX
);
708 sval
->value
= sval_type_max(sval
->type
).value
;
712 if (sval_cmp(sval_type_max(sval
->type
), *sval
) < 0)
713 sval
->value
= sval_type_max(sval
->type
).value
;
717 int known_condition_true(struct expression
*expr
)
724 if (get_value_sval(expr
, &tmp
) && tmp
.value
)
730 int known_condition_false(struct expression
*expr
)
738 if (expr
->type
== EXPR_CALL
) {
739 if (sym_name_is("__builtin_constant_p", expr
->fn
))
745 int implied_condition_true(struct expression
*expr
)
752 if (known_condition_true(expr
))
754 if (get_implied_value_sval(expr
, &tmp
) && tmp
.value
)
757 if (expr
->type
== EXPR_POSTOP
)
758 return implied_condition_true(expr
->unop
);
760 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_DECREMENT
)
761 return implied_not_equal(expr
->unop
, 1);
762 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_INCREMENT
)
763 return implied_not_equal(expr
->unop
, -1);
765 expr
= strip_expr(expr
);
766 switch (expr
->type
) {
768 if (do_comparison(expr
) == 1)
772 if (expr
->op
== '!') {
773 if (implied_condition_false(expr
->unop
))
779 if (implied_not_equal(expr
, 0) == 1)
786 int implied_condition_false(struct expression
*expr
)
788 struct expression
*tmp
;
794 if (known_condition_false(expr
))
797 switch (expr
->type
) {
799 if (do_comparison(expr
) == 2)
802 if (expr
->op
== '!') {
803 if (implied_condition_true(expr
->unop
))
807 tmp
= strip_expr(expr
);
809 return implied_condition_false(tmp
);
812 if (get_implied_value_sval(expr
, &sval
) && sval
.value
== 0)