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
};
35 static int opposite_implied(int implied
)
37 if (implied
== IMPLIED_MIN
)
39 if (implied
== IMPLIED_MAX
)
41 if (implied
== FUZZY_MIN
)
43 if (implied
== FUZZY_MAX
)
45 if (implied
== ABSOLUTE_MIN
)
47 if (implied
== ABSOLUTE_MAX
)
53 static int last_stmt_sval(struct statement
*stmt
, sval_t
*sval
)
55 struct expression
*expr
;
60 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
61 if (stmt
->type
!= STMT_EXPRESSION
)
63 expr
= stmt
->expression
;
64 if (!get_value(expr
, sval
))
69 static sval_t
handle_expression_statement(struct expression
*expr
, int *undefined
, int implied
)
71 struct statement
*stmt
;
74 stmt
= get_expression_statement(expr
);
75 if (!last_stmt_sval(stmt
, &ret
)) {
83 static sval_t
handle_ampersand(int *undefined
, int implied
)
87 ret
.type
= &ptr_ctype
;
90 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
)
91 return valid_ptr_min_sval
;
92 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
)
93 return valid_ptr_max_sval
;
99 static sval_t
handle_negate(struct expression
*expr
, int *undefined
, int implied
)
103 ret
= sval_blank(expr
->unop
);
104 if (implied_condition_true(expr
->unop
)) {
108 if (implied_condition_false(expr
->unop
)) {
112 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
) {
116 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
) {
124 static sval_t
handle_preop(struct expression
*expr
, int *undefined
, int implied
)
130 ret
= handle_ampersand(undefined
, implied
);
133 ret
= handle_negate(expr
, undefined
, implied
);
136 ret
= _get_value(expr
->unop
, undefined
, implied
);
137 ret
= sval_preop(ret
, '~');
138 ret
= sval_cast(get_type(expr
->unop
), ret
);
141 ret
= _get_value(expr
->unop
, undefined
, implied
);
142 ret
= sval_preop(ret
, '-');
145 ret
= _get_implied_value(expr
, undefined
, implied
);
148 ret
= handle_expression_statement(expr
, undefined
, implied
);
152 ret
= sval_blank(expr
);
154 ret
= sval_cast(get_type(expr
), ret
);
158 static sval_t
handle_divide(struct expression
*expr
, int *undefined
, int implied
)
162 left
= _get_value(expr
->left
, undefined
, implied
);
163 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
165 if (right
.value
== 0) {
170 return sval_binop(left
, '/', right
);
173 static sval_t
handle_subtract(struct expression
*expr
, int *undefined
, int implied
)
177 left
= _get_value(expr
->left
, undefined
, implied
);
178 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
180 return sval_binop(left
, '-', right
);
183 static sval_t
handle_binop(struct expression
*expr
, int *undefined
, int implied
)
186 sval_t ret
= {.type
= &int_ctype
, .value
= 123456};
191 left
= _get_value(expr
->left
, &local_undef
, implied
);
193 if (implied
== ABSOLUTE_MIN
) {
194 ret
= sval_blank(expr
->left
);
198 if (implied
!= ABSOLUTE_MAX
)
200 if (!get_absolute_max(expr
->left
, &left
))
203 right
= _get_value(expr
->right
, undefined
, implied
);
204 if (right
.value
== 0)
208 return sval_binop(left
, '%', right
);
211 left
= _get_value(expr
->left
, &local_undef
, implied
);
213 if (implied
== ABSOLUTE_MIN
) {
214 ret
= sval_blank(expr
->left
);
218 if (implied
!= ABSOLUTE_MAX
)
220 if (!get_absolute_max(expr
->left
, &left
))
223 right
= _get_value(expr
->right
, undefined
, implied
);
226 return sval_binop(left
, '&', right
);
228 case SPECIAL_RIGHTSHIFT
:
229 left
= _get_value(expr
->left
, &local_undef
, implied
);
231 if (implied
== ABSOLUTE_MIN
) {
232 ret
= sval_blank(expr
->left
);
236 if (implied
!= ABSOLUTE_MAX
)
238 if (!get_absolute_max(expr
->left
, &left
))
241 right
= _get_value(expr
->right
, undefined
, implied
);
244 return sval_binop(left
, SPECIAL_RIGHTSHIFT
, right
);
247 left
= _get_value(expr
->left
, undefined
, implied
);
248 right
= _get_value(expr
->right
, undefined
, implied
);
255 return handle_divide(expr
, undefined
, implied
);
257 if (right
.value
== 0) {
261 return sval_binop(left
, '%', right
);
264 ret
= handle_subtract(expr
, undefined
, implied
);
267 ret
= sval_binop(left
, expr
->op
, right
);
272 static int do_comparison(struct expression
*expr
)
274 struct range_list
*left_ranges
= NULL
;
275 struct range_list
*right_ranges
= NULL
;
276 int poss_true
, poss_false
;
278 get_implied_range_list(expr
->left
, &left_ranges
);
279 get_implied_range_list(expr
->right
, &right_ranges
);
281 poss_true
= possibly_true_range_lists(left_ranges
, expr
->op
, right_ranges
);
282 poss_false
= possibly_false_range_lists(left_ranges
, expr
->op
, right_ranges
);
284 free_range_list(&left_ranges
);
285 free_range_list(&right_ranges
);
287 if (!poss_true
&& !poss_false
)
289 if (poss_true
&& !poss_false
)
291 if (!poss_true
&& poss_false
)
296 static sval_t
handle_comparison(struct expression
*expr
, int *undefined
, int implied
)
301 if (get_value(expr
->left
, &left
) && get_value(expr
->right
, &right
)) {
302 struct data_range tmp_left
, tmp_right
;
306 tmp_right
.min
= right
;
307 tmp_right
.max
= right
;
308 if (true_comparison_range(&tmp_left
, expr
->op
, &tmp_right
))
313 if (implied
== NOTIMPLIED
) {
318 res
= do_comparison(expr
);
324 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
)
326 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
)
333 static sval_t
handle_logical(struct expression
*expr
, int *undefined
, int implied
)
337 if ((implied
== NOTIMPLIED
&& get_value(expr
->left
, &left
) &&
338 get_value(expr
->right
, &right
)) ||
339 (implied
!= NOTIMPLIED
&& get_implied_value(expr
->left
, &left
) &&
340 get_implied_value(expr
->right
, &right
))) {
342 case SPECIAL_LOGICAL_OR
:
343 if (left
.value
|| right
.value
)
346 case SPECIAL_LOGICAL_AND
:
347 if (left
.value
&& right
.value
)
356 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
)
358 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
)
365 static sval_t
handle_conditional(struct expression
*expr
, int *undefined
, int implied
)
367 if (known_condition_true(expr
->conditional
))
368 return _get_value(expr
->cond_true
, undefined
, implied
);
369 if (known_condition_false(expr
->conditional
))
370 return _get_value(expr
->cond_false
, undefined
, implied
);
372 if (implied
== NOTIMPLIED
) {
377 if (implied_condition_true(expr
->conditional
))
378 return _get_value(expr
->cond_true
, undefined
, implied
);
379 if (implied_condition_false(expr
->conditional
))
380 return _get_value(expr
->cond_false
, undefined
, implied
);
386 static int get_implied_value_helper(struct expression
*expr
, sval_t
*sval
, int implied
)
388 struct smatch_state
*state
;
392 /* fixme: this should return the casted value */
394 expr
= strip_expr(expr
);
396 if (get_value(expr
, sval
))
399 name
= get_variable_from_expr(expr
, &sym
);
402 *sval
= sval_blank(expr
);
403 state
= get_state(SMATCH_EXTRA
, name
, sym
);
405 if (!state
|| !state
->data
)
407 if (implied
== IMPLIED
) {
408 if (estate_get_single_value(state
, sval
))
412 if (implied
== HARD_MAX
) {
413 if (estate_get_hard_max(state
, sval
))
417 if (implied
== IMPLIED_MAX
) {
418 *sval
= estate_max(state
);
419 if (sval_is_max(*sval
)) /* this means just guessing. fixme. not really */
423 *sval
= estate_min(state
);
424 if (sval_is_min(*sval
)) /* fixme */
429 static int get_fuzzy_max_helper(struct expression
*expr
, sval_t
*max
)
432 struct sm_state
*tmp
;
435 if (get_hard_max(expr
, &sval
)) {
440 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
444 sval
= sval_type_min(estate_type(sm
->state
));
445 FOR_EACH_PTR(sm
->possible
, tmp
) {
448 new_min
= estate_min(tmp
->state
);
449 if (sval_cmp(new_min
, sval
) > 0)
451 } END_FOR_EACH_PTR(tmp
);
453 if (sval_is_min(sval
))
456 *max
= sval_cast(get_type(expr
), sval
);
460 static int get_fuzzy_min_helper(struct expression
*expr
, sval_t
*min
)
463 struct sm_state
*tmp
;
466 if (get_implied_min(expr
, min
))
469 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
473 sval
= sval_type_max(estate_type(sm
->state
));
474 FOR_EACH_PTR(sm
->possible
, tmp
) {
477 new_max
= estate_max(tmp
->state
);
478 if (sval_cmp(new_max
, sval
) < 0)
480 } END_FOR_EACH_PTR(tmp
);
482 if (sval_is_max(sval
))
484 *min
= sval_cast(get_type(expr
), sval
);
488 static sval_t
_get_implied_value(struct expression
*expr
, int *undefined
, int implied
)
492 ret
= sval_blank(expr
);
499 if (!get_implied_value_helper(expr
, &ret
, implied
))
503 if (!get_absolute_min_helper(expr
, &ret
))
507 if (!get_absolute_max_helper(expr
, &ret
))
511 if (!get_fuzzy_max_helper(expr
, &ret
))
515 if (!get_fuzzy_min_helper(expr
, &ret
))
524 static int get_const_value(struct expression
*expr
, sval_t
*sval
)
529 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
)
532 if (!(sym
->ctype
.modifiers
& MOD_CONST
))
534 if (get_value(sym
->initializer
, &right
)) {
535 *sval
= sval_cast(get_type(expr
), right
);
541 static sval_t
_get_value(struct expression
*expr
, int *undefined
, int implied
)
552 expr
= strip_parens(expr
);
554 switch (expr
->type
) {
556 ret
= sval_from_val(expr
, expr
->value
);
559 ret
= handle_preop(expr
, undefined
, implied
);
562 ret
= _get_value(expr
->unop
, undefined
, implied
);
565 case EXPR_FORCE_CAST
:
566 case EXPR_IMPLIED_CAST
:
567 ret
= _get_value(expr
->cast_expression
, undefined
, implied
);
568 ret
= sval_cast(get_type(expr
), ret
);
571 ret
= handle_binop(expr
, undefined
, implied
);
574 ret
= handle_comparison(expr
, undefined
, implied
);
577 ret
= handle_logical(expr
, undefined
, implied
);
581 ret
= sval_blank(expr
);
582 ret
.value
= get_expression_value_nomod(expr
);
585 if (get_const_value(expr
, &ret
)) {
588 ret
= _get_implied_value(expr
, undefined
, implied
);
591 case EXPR_CONDITIONAL
:
592 ret
= handle_conditional(expr
, undefined
, implied
);
595 ret
= _get_implied_value(expr
, undefined
, implied
);
602 /* returns 1 if it can get a value literal or else returns 0 */
603 int get_value(struct expression
*expr
, sval_t
*sval
)
608 ret
= _get_value(expr
, &undefined
, NOTIMPLIED
);
615 int get_implied_value(struct expression
*expr
, sval_t
*sval
)
620 ret
= _get_value(expr
, &undefined
, IMPLIED
);
627 int get_implied_min(struct expression
*expr
, sval_t
*sval
)
632 ret
= _get_value(expr
, &undefined
, IMPLIED_MIN
);
639 int get_implied_max(struct expression
*expr
, sval_t
*sval
)
644 ret
= _get_value(expr
, &undefined
, IMPLIED_MAX
);
651 int get_hard_max(struct expression
*expr
, sval_t
*sval
)
656 ret
= _get_value(expr
, &undefined
, HARD_MAX
);
663 int get_fuzzy_min(struct expression
*expr
, sval_t
*sval
)
668 ret
= _get_value(expr
, &undefined
, FUZZY_MIN
);
675 int get_fuzzy_max(struct expression
*expr
, sval_t
*sval
)
680 ret
= _get_value(expr
, &undefined
, FUZZY_MAX
);
687 int get_absolute_min(struct expression
*expr
, sval_t
*sval
)
692 type
= get_type(expr
);
694 type
= &llong_ctype
; // FIXME: this is wrong but places assume get type can't fail.
695 *sval
= _get_value(expr
, &undefined
, ABSOLUTE_MIN
);
697 *sval
= sval_type_min(type
);
701 if (sval_cmp(*sval
, sval_type_min(type
)) < 0)
702 *sval
= sval_type_min(type
);
706 int get_absolute_max(struct expression
*expr
, sval_t
*sval
)
711 type
= get_type(expr
);
714 *sval
= _get_value(expr
, &undefined
, ABSOLUTE_MAX
);
716 *sval
= sval_type_max(type
);
720 if (sval_cmp(sval_type_max(type
), *sval
) < 0)
721 *sval
= sval_type_max(type
);
725 int known_condition_true(struct expression
*expr
)
732 if (get_value(expr
, &tmp
) && tmp
.value
)
738 int known_condition_false(struct expression
*expr
)
746 if (expr
->type
== EXPR_CALL
) {
747 if (sym_name_is("__builtin_constant_p", expr
->fn
))
753 int implied_condition_true(struct expression
*expr
)
760 if (known_condition_true(expr
))
762 if (get_implied_value(expr
, &tmp
) && tmp
.value
)
765 if (expr
->type
== EXPR_POSTOP
)
766 return implied_condition_true(expr
->unop
);
768 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_DECREMENT
)
769 return implied_not_equal(expr
->unop
, 1);
770 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_INCREMENT
)
771 return implied_not_equal(expr
->unop
, -1);
773 expr
= strip_expr(expr
);
774 switch (expr
->type
) {
776 if (do_comparison(expr
) == 1)
780 if (expr
->op
== '!') {
781 if (implied_condition_false(expr
->unop
))
787 if (implied_not_equal(expr
, 0) == 1)
794 int implied_condition_false(struct expression
*expr
)
796 struct expression
*tmp
;
802 if (known_condition_false(expr
))
805 switch (expr
->type
) {
807 if (do_comparison(expr
) == 2)
810 if (expr
->op
== '!') {
811 if (implied_condition_true(expr
->unop
))
815 tmp
= strip_expr(expr
);
817 return implied_condition_false(tmp
);
820 if (get_implied_value(expr
, &sval
) && sval
.value
== 0)