2 * sparse/smatch_extra.c
4 * Copyright (C) 2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
11 * smatch_extra.c is supposed to track the value of every variable.
21 #include "smatch_slist.h"
22 #include "smatch_extra.h"
26 static struct symbol
*cur_func
;
28 struct data_range whole_range
= {
33 static struct smatch_state
*alloc_extra_state_empty(void)
35 struct smatch_state
*state
;
36 struct data_info
*dinfo
;
38 dinfo
= __alloc_data_info(0);
39 dinfo
->type
= DATA_RANGE
;
40 dinfo
->value_ranges
= NULL
;
41 state
= __alloc_smatch_state(0);
46 static struct smatch_state
*alloc_extra_state_no_name(int val
)
48 struct smatch_state
*state
;
50 state
= __alloc_smatch_state(0);
51 state
->data
= (void *)alloc_dinfo_range(val
, val
);
55 /* We do this because ->value_ranges is a list */
56 struct smatch_state
*extra_undefined(void)
58 struct data_info
*dinfo
;
59 static struct smatch_state
*ret
;
60 static struct symbol
*prev_func
;
62 if (prev_func
== cur_func
)
66 dinfo
= alloc_dinfo_range(whole_range
.min
, whole_range
.max
);
67 ret
= __alloc_smatch_state(0);
68 ret
->name
= "unknown";
73 struct smatch_state
*alloc_extra_state(long long val
)
75 struct smatch_state
*state
;
77 state
= alloc_extra_state_no_name(val
);
78 state
->name
= show_ranges(get_dinfo(state
)->value_ranges
);
82 struct smatch_state
*alloc_extra_state_range(long long min
, long long max
)
84 struct smatch_state
*state
;
86 if (min
== whole_range
.min
&& max
== whole_range
.max
)
87 return extra_undefined();
88 state
= __alloc_smatch_state(0);
89 state
->data
= (void *)alloc_dinfo_range(min
, max
);
90 state
->name
= show_ranges(get_dinfo(state
)->value_ranges
);
94 struct smatch_state
*alloc_extra_state_range_list(struct range_list
*rl
)
96 struct smatch_state
*state
;
98 state
= __alloc_smatch_state(0);
99 state
->data
= (void *)alloc_dinfo_range_list(rl
);
100 state
->name
= show_ranges(get_dinfo(state
)->value_ranges
);
104 struct data_info
*get_dinfo(struct smatch_state
*state
)
108 return (struct data_info
*)state
->data
;
112 struct smatch_state
*filter_range(struct smatch_state
*orig
,
113 long long filter_min
, long long filter_max
)
115 struct smatch_state
*ret
;
116 struct data_info
*orig_info
;
117 struct data_info
*ret_info
;
120 orig
= extra_undefined();
121 orig_info
= get_dinfo(orig
);
122 ret
= alloc_extra_state_empty();
123 ret_info
= get_dinfo(ret
);
124 ret_info
->value_ranges
= remove_range(orig_info
->value_ranges
, filter_min
, filter_max
);
125 ret
->name
= show_ranges(ret_info
->value_ranges
);
129 struct smatch_state
*add_filter(struct smatch_state
*orig
, long long num
)
131 return filter_range(orig
, num
, num
);
134 static struct smatch_state
*merge_func(const char *name
, struct symbol
*sym
,
135 struct smatch_state
*s1
,
136 struct smatch_state
*s2
)
138 struct data_info
*info1
= get_dinfo(s1
);
139 struct data_info
*info2
= get_dinfo(s2
);
140 struct data_info
*ret_info
;
141 struct smatch_state
*tmp
;
142 struct range_list
*value_ranges
;
144 value_ranges
= range_list_union(info1
->value_ranges
, info2
->value_ranges
);
145 tmp
= alloc_extra_state_empty();
146 ret_info
= get_dinfo(tmp
);
147 ret_info
->value_ranges
= value_ranges
;
148 tmp
->name
= show_ranges(ret_info
->value_ranges
);
152 void __extra_handle_canonical_for_loop(struct statement
*loop
)
154 struct expression
*iter_expr
;
155 struct expression
*iter_var
;
156 struct expression
*condition
;
161 if (!loop
->iterator_post_statement
)
163 if (loop
->iterator_post_statement
->type
!= STMT_EXPRESSION
)
165 iter_expr
= loop
->iterator_post_statement
->expression
;
166 if (!loop
->iterator_pre_condition
)
168 if (loop
->iterator_pre_condition
->type
!= EXPR_COMPARE
)
170 condition
= loop
->iterator_pre_condition
;
173 if (iter_expr
->op
!= SPECIAL_INCREMENT
)
175 iter_var
= iter_expr
->unop
;
176 sm
= get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
179 if (!get_single_value_from_dinfo(get_dinfo(sm
->state
), &start
))
181 if (!get_value(condition
->right
, &end
))
183 if (get_sm_state_expr(SMATCH_EXTRA
, condition
->left
) != sm
)
186 switch (condition
->op
) {
187 case SPECIAL_NOTEQUAL
:
188 set_state_expr(SMATCH_EXTRA
, iter_var
, alloc_extra_state_range(start
, end
- 1));
191 set_state_expr(SMATCH_EXTRA
, iter_var
, alloc_extra_state_range(start
, end
- 1));
194 set_state_expr(SMATCH_EXTRA
, iter_var
, alloc_extra_state_range(start
, end
));
199 struct sm_state
*__extra_pre_loop_hook_before(struct statement
*iterator_pre_statement
)
201 struct expression
*expr
;
204 struct sm_state
*ret
= NULL
;
206 if (!iterator_pre_statement
)
208 if (iterator_pre_statement
->type
!= STMT_EXPRESSION
)
210 expr
= iterator_pre_statement
->expression
;
211 if (expr
->type
!= EXPR_ASSIGNMENT
)
213 name
= get_variable_from_expr(expr
->left
, &sym
);
216 ret
= get_sm_state(my_id
, name
, sym
);
222 int __iterator_unchanged(struct sm_state
*sm
, struct statement
*iterator
)
224 struct expression
*iter_expr
;
231 if (iterator
->type
!= STMT_EXPRESSION
)
233 iter_expr
= iterator
->expression
;
234 if (iter_expr
->op
!= SPECIAL_INCREMENT
&& iter_expr
->op
!= SPECIAL_DECREMENT
)
236 name
= get_variable_from_expr(iter_expr
->unop
, &sym
);
239 if (get_sm_state(my_id
, name
, sym
) == sm
)
246 void __extra_pre_loop_hook_after(struct sm_state
*sm
,
247 struct statement
*iterator
,
248 struct expression
*condition
)
250 struct expression
*iter_expr
;
255 struct smatch_state
*state
;
256 struct data_info
*dinfo
;
259 iter_expr
= iterator
->expression
;
261 if (condition
->type
!= EXPR_COMPARE
)
263 if (!get_value(condition
->left
, &value
)) {
264 if (!get_value(condition
->right
, &value
))
269 name
= get_variable_from_expr(condition
->left
, &sym
);
271 name
= get_variable_from_expr(condition
->right
, &sym
);
274 if (sym
!= sm
->sym
|| strcmp(name
, sm
->name
))
276 state
= get_state(my_id
, name
, sym
);
277 dinfo
= get_dinfo(state
);
278 min
= get_dinfo_min(dinfo
);
279 max
= get_dinfo_max(dinfo
);
280 if (iter_expr
->op
== SPECIAL_INCREMENT
&& min
!= whole_range
.min
&& max
== whole_range
.max
) {
281 set_state(my_id
, name
, sym
, alloc_extra_state(min
));
282 } else if (min
== whole_range
.min
&& max
!= whole_range
.max
) {
283 set_state(my_id
, name
, sym
, alloc_extra_state(max
));
290 static struct smatch_state
*unmatched_state(struct sm_state
*sm
)
292 return extra_undefined();
295 static void match_function_call(struct expression
*expr
)
297 struct expression
*tmp
;
302 FOR_EACH_PTR(expr
->args
, tmp
) {
303 if (tmp
->type
== EXPR_PREOP
&& tmp
->op
== '&') {
304 name
= get_variable_from_expr(tmp
->unop
, &sym
);
306 set_state(my_id
, name
, sym
, extra_undefined());
311 } END_FOR_EACH_PTR(tmp
);
314 static void match_assign(struct expression
*expr
)
316 struct expression
*left
;
317 struct expression
*right
;
322 long long min
= whole_range
.min
;
323 long long max
= whole_range
.max
;
325 struct range_list
*rl
= NULL
;
327 left
= strip_expr(expr
->left
);
328 name
= get_variable_from_expr(left
, &sym
);
331 right
= strip_expr(expr
->right
);
332 while (right
->type
== EXPR_ASSIGNMENT
&& right
->op
== '=')
333 right
= strip_expr(right
->left
);
335 known
= get_implied_range_list(right
, &rl
);
336 if (expr
->op
== '=') {
338 set_state(my_id
, name
, sym
, alloc_extra_state_range_list(rl
));
340 set_state(my_id
, name
, sym
, extra_undefined());
344 known
= get_implied_value(right
, &value
);
345 if (expr
->op
== SPECIAL_ADD_ASSIGN
) {
346 if (get_implied_min(left
, &tmp
)) {
354 if (expr
->op
== SPECIAL_SUB_ASSIGN
) {
355 if (get_implied_max(left
, &tmp
)) {
363 set_state(my_id
, name
, sym
, alloc_extra_state_range(min
, max
));
368 static void unop_expr(struct expression
*expr
)
372 long long min
= whole_range
.min
;
373 long long max
= whole_range
.max
;
383 name
= get_variable_from_expr(expr
->unop
, &sym
);
386 if (expr
->op
== SPECIAL_INCREMENT
) {
387 if (get_implied_min(expr
->unop
, &val
))
390 if (expr
->op
== SPECIAL_DECREMENT
) {
391 if (get_implied_max(expr
->unop
, &val
))
394 set_state(my_id
, name
, sym
, alloc_extra_state_range(min
, max
));
399 static void match_declarations(struct symbol
*sym
)
405 name
= sym
->ident
->name
;
406 if (sym
->initializer
) {
407 if (get_value(sym
->initializer
, &val
))
408 set_state(my_id
, name
, sym
, alloc_extra_state(val
));
410 set_state(my_id
, name
, sym
, extra_undefined());
411 scoped_state(my_id
, name
, sym
);
413 set_state(my_id
, name
, sym
, extra_undefined());
414 scoped_state(my_id
, name
, sym
);
419 static void match_function_def(struct symbol
*sym
)
424 FOR_EACH_PTR(sym
->ctype
.base_type
->arguments
, arg
) {
428 set_state(my_id
, arg
->ident
->name
, arg
, extra_undefined());
429 } END_FOR_EACH_PTR(arg
);
436 static int get_implied_value_helper(struct expression
*expr
, long long *val
, int what
)
438 struct smatch_state
*state
;
442 if (get_value(expr
, val
))
445 name
= get_variable_from_expr(expr
, &sym
);
448 state
= get_state(my_id
, name
, sym
);
450 if (!state
|| !state
->data
)
452 if (what
== VAL_SINGLE
)
453 return get_single_value_from_dinfo(get_dinfo(state
), val
);
454 if (what
== VAL_MAX
) {
455 *val
= get_dinfo_max(get_dinfo(state
));
456 if (*val
== whole_range
.max
) /* this means just guessing */
460 *val
= get_dinfo_min(get_dinfo(state
));
461 if (*val
== whole_range
.min
)
466 int get_implied_single_val(struct expression
*expr
, long long *val
)
468 return get_implied_value_helper(expr
, val
, VAL_SINGLE
);
471 int get_implied_max(struct expression
*expr
, long long *val
)
473 return get_implied_value_helper(expr
, val
, VAL_MAX
);
476 int get_implied_min(struct expression
*expr
, long long *val
)
478 return get_implied_value_helper(expr
, val
, VAL_MIN
);
481 int get_implied_single_fuzzy_max(struct expression
*expr
, long long *max
)
484 struct sm_state
*tmp
;
486 if (get_implied_max(expr
, max
))
489 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
493 *max
= whole_range
.min
;
494 FOR_EACH_PTR(sm
->possible
, tmp
) {
497 new_min
= get_dinfo_min(get_dinfo(tmp
->state
));
500 } END_FOR_EACH_PTR(tmp
);
502 if (*max
> whole_range
.min
)
507 int get_implied_single_fuzzy_min(struct expression
*expr
, long long *min
)
510 struct sm_state
*tmp
;
512 if (get_implied_min(expr
, min
))
515 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
519 *min
= whole_range
.max
;
520 FOR_EACH_PTR(sm
->possible
, tmp
) {
523 new_max
= get_dinfo_max(get_dinfo(tmp
->state
));
526 } END_FOR_EACH_PTR(tmp
);
528 if (*min
< whole_range
.max
)
533 static int last_stmt_val(struct statement
*stmt
, long long *val
)
535 struct expression
*expr
;
540 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
541 if (stmt
->type
!= STMT_EXPRESSION
)
543 expr
= stmt
->expression
;
544 return get_value(expr
, val
);
547 static void match_comparison(struct expression
*expr
)
552 struct smatch_state
*one_state
;
553 struct smatch_state
*two_state
;
554 struct smatch_state
*orig
;
556 int comparison
= expr
->op
;
557 struct expression
*varies
= expr
->right
;
559 if (!get_value(expr
->left
, &fixed
)) {
560 if (!get_value(expr
->right
, &fixed
))
565 if (varies
->op
== SPECIAL_INCREMENT
|| varies
->op
== SPECIAL_DECREMENT
)
566 varies
= varies
->unop
;
567 if (varies
->type
== EXPR_CALL
) {
568 function_comparison(comparison
, varies
, fixed
, left
);
572 name
= get_variable_from_expr(varies
, &sym
);
576 orig
= get_state(my_id
, name
, sym
);
578 orig
= extra_undefined();
580 switch (comparison
) {
582 case SPECIAL_UNSIGNED_LT
:
583 one_state
= filter_range(orig
, whole_range
.min
, fixed
- 1);
584 two_state
= filter_range(orig
, fixed
, whole_range
.max
);
586 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
588 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
590 case SPECIAL_UNSIGNED_LTE
:
592 one_state
= filter_range(orig
, whole_range
.min
, fixed
);
593 two_state
= filter_range(orig
, fixed
+ 1, whole_range
.max
);
595 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
597 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
600 // todo. print a warning here for impossible conditions.
601 one_state
= alloc_extra_state(fixed
);
602 two_state
= filter_range(orig
, fixed
, fixed
);
603 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
605 case SPECIAL_UNSIGNED_GTE
:
607 one_state
= filter_range(orig
, whole_range
.min
, fixed
- 1);
608 two_state
= filter_range(orig
, fixed
, whole_range
.max
);
610 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
612 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
615 case SPECIAL_UNSIGNED_GT
:
616 one_state
= filter_range(orig
, whole_range
.min
, fixed
);
617 two_state
= filter_range(orig
, fixed
+ 1, whole_range
.max
);
619 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
621 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
623 case SPECIAL_NOTEQUAL
:
624 one_state
= alloc_extra_state(fixed
);
625 two_state
= filter_range(orig
, fixed
, fixed
);
626 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
629 sm_msg("unhandled comparison %d\n", comparison
);
637 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
638 void __extra_match_condition(struct expression
*expr
)
642 struct smatch_state
*pre_state
;
643 struct smatch_state
*true_state
;
644 struct smatch_state
*false_state
;
646 expr
= strip_expr(expr
);
647 switch (expr
->type
) {
649 function_comparison(SPECIAL_NOTEQUAL
, expr
, 0, 1);
654 name
= get_variable_from_expr(expr
, &sym
);
657 pre_state
= get_state(my_id
, name
, sym
);
658 true_state
= add_filter(pre_state
, 0);
659 false_state
= alloc_extra_state(0);
660 set_true_false_states(my_id
, name
, sym
, true_state
, false_state
);
664 match_comparison(expr
);
666 case EXPR_ASSIGNMENT
:
667 __extra_match_condition(expr
->left
);
672 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
673 int implied_not_equal(struct expression
*expr
, long long val
)
677 struct smatch_state
*state
;
680 name
= get_variable_from_expr(expr
, &sym
);
683 state
= get_state(my_id
, name
, sym
);
684 if (!state
|| !state
->data
)
686 ret
= !possibly_false(SPECIAL_NOTEQUAL
, get_dinfo(state
), val
, 1);
692 int known_condition_true(struct expression
*expr
)
699 if (get_value(expr
, &tmp
) && tmp
)
702 expr
= strip_expr(expr
);
703 switch (expr
->type
) {
705 if (expr
->op
== '!') {
706 if (known_condition_false(expr
->unop
))
717 int known_condition_false(struct expression
*expr
)
725 switch (expr
->type
) {
727 if (expr
->op
== '!') {
728 if (known_condition_true(expr
->unop
))
739 static int do_comparison_range(struct expression
*expr
)
743 struct smatch_state
*state
;
746 int poss_true
, poss_false
;
748 if (!get_value(expr
->left
, &value
)) {
749 if (!get_value(expr
->right
, &value
))
754 name
= get_variable_from_expr(expr
->left
, &sym
);
756 name
= get_variable_from_expr(expr
->right
, &sym
);
759 state
= get_state(SMATCH_EXTRA
, name
, sym
);
762 poss_true
= possibly_true(expr
->op
, get_dinfo(state
), value
, left
);
763 poss_false
= possibly_false(expr
->op
, get_dinfo(state
), value
, left
);
764 if (!poss_true
&& !poss_false
)
766 if (poss_true
&& !poss_false
)
768 if (!poss_true
&& poss_false
)
770 if (poss_true
&& poss_false
)
777 int implied_condition_true(struct expression
*expr
)
779 struct statement
*stmt
;
786 if (get_value(expr
, &tmp
) && tmp
)
789 expr
= strip_expr(expr
);
790 switch (expr
->type
) {
792 if (do_comparison_range(expr
) == 1)
796 if (expr
->op
== '!') {
797 if (implied_condition_false(expr
->unop
))
801 stmt
= get_block_thing(expr
);
802 if (last_stmt_val(stmt
, &val
) && val
== 1)
806 if (implied_not_equal(expr
, 0) == 1)
813 int implied_condition_false(struct expression
*expr
)
815 struct statement
*stmt
;
816 struct expression
*tmp
;
825 switch (expr
->type
) {
827 if (do_comparison_range(expr
) == 2)
830 if (expr
->op
== '!') {
831 if (implied_condition_true(expr
->unop
))
835 stmt
= get_block_thing(expr
);
836 if (last_stmt_val(stmt
, &val
) && val
== 0)
838 tmp
= strip_expr(expr
);
840 return implied_condition_false(tmp
);
843 if (get_implied_value(expr
, &val
) && val
== 0)
850 int get_implied_range_list(struct expression
*expr
, struct range_list
**rl
)
853 struct smatch_state
*state
;
855 expr
= strip_expr(expr
);
857 state
= get_state_expr(my_id
, expr
);
859 *rl
= clone_range_list(get_dinfo(state
)->value_ranges
);
863 if (get_implied_value(expr
, &val
)) {
865 add_range(rl
, val
, val
);
869 if (expr
->type
== EXPR_BINOP
&& expr
->op
== '%') {
870 if (!get_implied_value(expr
->right
, &val
))
873 add_range(rl
, 0, val
- 1);
880 void register_smatch_extra(int id
)
883 add_merge_hook(my_id
, &merge_func
);
884 add_unmatched_state_hook(my_id
, &unmatched_state
);
885 add_hook(&unop_expr
, OP_HOOK
);
886 add_hook(&match_function_def
, FUNC_DEF_HOOK
);
887 add_hook(&match_function_call
, FUNCTION_CALL_HOOK
);
888 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
889 add_hook(&match_declarations
, DECLARATION_HOOK
);