2 * sparse/smatch_extra.c
4 * Copyright (C) 2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
15 #include "smatch_slist.h"
16 #include "smatch_extra.h"
20 static struct symbol
*cur_func
;
22 struct data_range whole_range
= {
27 static struct smatch_state
*alloc_extra_state_empty()
29 struct smatch_state
*state
;
30 struct data_info
*dinfo
;
32 dinfo
= __alloc_data_info(0);
33 dinfo
->type
= DATA_RANGE
;
35 dinfo
->value_ranges
= NULL
;
36 state
= __alloc_smatch_state(0);
41 static struct smatch_state
*alloc_extra_state_no_name(int val
)
43 struct smatch_state
*state
;
45 state
= __alloc_smatch_state(0);
47 state
->data
= (void *)alloc_dinfo_range(whole_range
.min
, whole_range
.max
);
49 state
->data
= (void *)alloc_dinfo_range(val
, val
);
53 /* We do this because ->value_ranges is a list */
54 struct smatch_state
*extra_undefined()
56 struct data_info
*dinfo
;
57 static struct smatch_state
*ret
;
58 static struct symbol
*prev_func
;
60 if (prev_func
== cur_func
)
64 dinfo
= alloc_dinfo_range(whole_range
.min
, whole_range
.max
);
65 ret
= __alloc_smatch_state(0);
66 ret
->name
= "unknown";
72 /* This is like extra_undefined() except merged. */
73 struct smatch_state
*min_max_merged()
75 struct data_info
*dinfo
;
76 static struct smatch_state
*ret
;
77 static struct symbol
*prev_func
;
79 if (prev_func
== cur_func
)
83 dinfo
= alloc_dinfo_range(whole_range
.min
, whole_range
.max
);
85 ret
= __alloc_smatch_state(0);
86 ret
->name
= "whole_range";
91 struct smatch_state
*alloc_extra_state(int val
)
93 struct smatch_state
*state
;
96 return extra_undefined();
97 state
= alloc_extra_state_no_name(val
);
98 state
->name
= show_ranges(((struct data_info
*)state
->data
)->value_ranges
);
102 struct smatch_state
*alloc_extra_state_range(long long min
, long long max
)
104 struct smatch_state
*state
;
106 if (min
== whole_range
.min
&& max
== whole_range
.max
)
107 return extra_undefined();
108 state
= __alloc_smatch_state(0);
109 state
->data
= (void *)alloc_dinfo_range(min
, max
);
110 state
->name
= show_ranges(((struct data_info
*)state
->data
)->value_ranges
);
114 struct smatch_state
*filter_range(struct smatch_state
*orig
,
115 long long filter_min
, long long filter_max
)
117 struct smatch_state
*ret
;
118 struct data_info
*orig_info
;
119 struct data_info
*ret_info
;
122 orig
= extra_undefined();
123 orig_info
= (struct data_info
*)orig
->data
;
124 ret
= alloc_extra_state_empty();
125 ret_info
= (struct data_info
*)ret
->data
;
126 ret_info
->value_ranges
= remove_range(orig_info
->value_ranges
, filter_min
, filter_max
);
127 ret
->name
= show_ranges(ret_info
->value_ranges
);
131 struct smatch_state
*add_filter(struct smatch_state
*orig
, long long num
)
133 return filter_range(orig
, num
, num
);
136 static struct smatch_state
*merge_func(const char *name
, struct symbol
*sym
,
137 struct smatch_state
*s1
,
138 struct smatch_state
*s2
)
140 struct data_info
*info1
= (struct data_info
*)s1
->data
;
141 struct data_info
*info2
= (struct data_info
*)s2
->data
;
142 struct data_info
*ret_info
;
143 struct smatch_state
*tmp
;
144 struct range_list
*value_ranges
;
146 value_ranges
= range_list_union(info1
->value_ranges
, info2
->value_ranges
);
147 if (is_whole_range(value_ranges
))
148 return min_max_merged();
149 tmp
= alloc_extra_state_empty();
150 ret_info
= (struct data_info
*)tmp
->data
;
151 ret_info
->merged
= 1;
152 ret_info
->value_ranges
= value_ranges
;
153 tmp
->name
= show_ranges(ret_info
->value_ranges
);
157 struct sm_state
*__extra_merge(struct sm_state
*one
, struct state_list
*slist1
,
158 struct sm_state
*two
, struct state_list
*slist2
)
160 struct data_info
*info1
;
161 struct data_info
*info2
;
163 if (!one
->state
->data
|| !two
->state
->data
) {
164 smatch_msg("internal error in smatch extra '%s = %s or %s'",
165 one
->name
, show_state(one
->state
),
166 show_state(two
->state
));
167 return alloc_state(one
->name
, one
->owner
, one
->sym
,
171 info1
= (struct data_info
*)one
->state
->data
;
172 info2
= (struct data_info
*)two
->state
->data
;
175 free_stack(&one
->my_pools
);
177 free_stack(&two
->my_pools
);
179 if (one
== two
&& !one
->my_pools
) {
180 add_pool(&one
->my_pools
, slist1
);
181 add_pool(&one
->my_pools
, slist2
);
184 add_pool(&one
->my_pools
, slist1
);
186 add_pool(&two
->my_pools
, slist2
);
189 add_pool(&one
->all_pools
, slist1
);
190 add_pool(&two
->all_pools
, slist2
);
191 return merge_sm_states(one
, two
);
194 struct sm_state
*__extra_and_merge(struct sm_state
*sm
,
195 struct state_list_stack
*stack
)
197 struct state_list
*slist
;
198 struct sm_state
*ret
= NULL
;
199 struct sm_state
*tmp
;
202 FOR_EACH_PTR(stack
, slist
) {
204 ret
= get_sm_state_slist(slist
, sm
->name
, sm
->owner
,
207 tmp
= get_sm_state_slist(slist
, sm
->name
, sm
->owner
,
209 ret
= merge_sm_states(ret
, tmp
);
211 } END_FOR_EACH_PTR(slist
);
213 smatch_msg("Internal error in __extra_and_merge");
216 ret
->my_pools
= stack
;
217 ret
->all_pools
= clone_stack(stack
);
221 struct sm_state
*__extra_pre_loop_hook_before(struct statement
*iterator_pre_statement
)
223 struct expression
*expr
;
226 struct sm_state
*ret
= NULL
;
228 if (!iterator_pre_statement
)
230 if (iterator_pre_statement
->type
!= STMT_EXPRESSION
)
232 expr
= iterator_pre_statement
->expression
;
233 if (expr
->type
!= EXPR_ASSIGNMENT
)
235 name
= get_variable_from_expr(expr
->left
, &sym
);
238 ret
= get_sm_state(name
, my_id
, sym
);
244 static const char *get_iter_op(struct expression
*expr
)
246 if (expr
->type
!= EXPR_POSTOP
&& expr
->type
!= EXPR_PREOP
)
248 return show_special(expr
->op
);
251 int __iterator_unchanged(struct sm_state
*sm
, struct statement
*iterator
)
253 struct expression
*iter_expr
;
261 if (iterator
->type
!= STMT_EXPRESSION
)
263 iter_expr
= iterator
->expression
;
264 op
= get_iter_op(iter_expr
);
265 if (!op
|| (strcmp(op
, "--") && strcmp(op
, "++")))
267 name
= get_variable_from_expr(iter_expr
->unop
, &sym
);
270 if (get_sm_state(name
, my_id
, sym
) == sm
)
277 void __extra_pre_loop_hook_after(struct sm_state
*sm
,
278 struct statement
*iterator
,
279 struct expression
*condition
)
281 struct expression
*iter_expr
;
287 struct smatch_state
*state
;
288 struct data_info
*dinfo
;
291 iter_expr
= iterator
->expression
;
293 if (condition
->type
!= EXPR_COMPARE
)
295 value
= get_value(condition
->left
);
296 if (value
== UNDEFINED
) {
297 value
= get_value(condition
->right
);
298 if (value
== UNDEFINED
)
303 name
= get_variable_from_expr(condition
->left
, &sym
);
305 name
= get_variable_from_expr(condition
->right
, &sym
);
308 if (sym
!= sm
->sym
|| strcmp(name
, sm
->name
))
310 op
= get_iter_op(iter_expr
);
311 state
= get_state(name
, my_id
, sym
);
312 dinfo
= (struct data_info
*)state
->data
;
313 min
= get_dinfo_min(dinfo
);
314 max
= get_dinfo_max(dinfo
);
315 if (!strcmp(op
, "++") && min
!= whole_range
.min
&& max
== whole_range
.max
) {
316 set_state(name
, my_id
, sym
, alloc_extra_state(min
));
317 } else if (min
== whole_range
.min
&& max
!= whole_range
.max
) {
318 set_state(name
, my_id
, sym
, alloc_extra_state(max
));
325 static struct smatch_state
*unmatched_state(struct sm_state
*sm
)
327 return extra_undefined();
330 static void match_function_call(struct expression
*expr
)
332 struct expression
*tmp
;
337 FOR_EACH_PTR(expr
->args
, tmp
) {
338 if (tmp
->op
== '&') {
339 name
= get_variable_from_expr(tmp
->unop
, &sym
);
341 set_state(name
, my_id
, sym
, extra_undefined());
346 } END_FOR_EACH_PTR(tmp
);
349 static void match_assign(struct expression
*expr
)
351 struct expression
*left
;
355 left
= strip_expr(expr
->left
);
356 name
= get_variable_from_expr(left
, &sym
);
359 set_state(name
, my_id
, sym
, alloc_extra_state(get_value(expr
->right
)));
363 static void undef_expr(struct expression
*expr
)
368 name
= get_variable_from_expr(expr
->unop
, &sym
);
371 if (!get_state(name
, my_id
, sym
)) {
375 set_state(name
, my_id
, sym
, extra_undefined());
379 static void match_declarations(struct symbol
*sym
)
384 name
= sym
->ident
->name
;
385 if (sym
->initializer
) {
386 set_state(name
, my_id
, sym
, alloc_extra_state(get_value(sym
->initializer
)));
388 set_state(name
, my_id
, sym
, extra_undefined());
393 static void match_function_def(struct symbol
*sym
)
398 FOR_EACH_PTR(sym
->ctype
.base_type
->arguments
, arg
) {
402 set_state(arg
->ident
->name
, my_id
, arg
, extra_undefined());
403 } END_FOR_EACH_PTR(arg
);
406 static void match_unop(struct expression
*expr
)
413 name
= get_variable_from_expr(expr
->unop
, &sym
);
417 tmp
= show_special(expr
->op
);
418 if ((!strcmp(tmp
, "--")) || (!strcmp(tmp
, "++")))
419 set_state(name
, my_id
, sym
, extra_undefined());
423 int get_implied_value(struct expression
*expr
)
425 struct smatch_state
*state
;
430 val
= get_value(expr
);
431 if (val
!= UNDEFINED
)
434 name
= get_variable_from_expr(expr
, &sym
);
437 state
= get_state(name
, my_id
, sym
);
439 if (!state
|| !state
->data
)
441 return get_single_value_from_range((struct data_info
*)state
->data
);
444 int last_stmt_val(struct statement
*stmt
)
446 struct expression
*expr
;
448 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
449 if (stmt
->type
!= STMT_EXPRESSION
)
451 expr
= stmt
->expression
;
452 return get_value(expr
);
455 static void match_comparison(struct expression
*expr
)
460 struct smatch_state
*one_state
;
461 struct smatch_state
*two_state
;
462 struct smatch_state
*orig
;
464 int comparison
= expr
->op
;
466 value
= get_value(expr
->left
);
467 if (value
== UNDEFINED
) {
468 value
= get_value(expr
->right
);
469 if (value
== UNDEFINED
)
474 name
= get_variable_from_expr(expr
->left
, &sym
);
476 name
= get_variable_from_expr(expr
->right
, &sym
);
480 orig
= get_state(name
, my_id
, sym
);
482 orig
= extra_undefined();
486 case SPECIAL_UNSIGNED_LT
:
487 one_state
= filter_range(orig
, whole_range
.min
, value
- 1);
488 two_state
= filter_range(orig
, value
, whole_range
.max
);
490 set_true_false_states(name
, my_id
, sym
, two_state
, one_state
);
492 set_true_false_states(name
, my_id
, sym
, one_state
, two_state
);
494 case SPECIAL_UNSIGNED_LTE
:
496 one_state
= filter_range(orig
, whole_range
.min
, value
);
497 two_state
= filter_range(orig
, value
+ 1, whole_range
.max
);
499 set_true_false_states(name
, my_id
, sym
, two_state
, one_state
);
501 set_true_false_states(name
, my_id
, sym
, one_state
, two_state
);
504 // todo. print a warning here for impossible conditions.
505 one_state
= alloc_extra_state(value
);
506 two_state
= filter_range(orig
, value
, value
);
507 set_true_false_states(name
, my_id
, sym
, one_state
, two_state
);
509 case SPECIAL_UNSIGNED_GTE
:
511 one_state
= filter_range(orig
, whole_range
.min
, value
- 1);
512 two_state
= filter_range(orig
, value
, whole_range
.max
);
514 set_true_false_states(name
, my_id
, sym
, one_state
, two_state
);
516 set_true_false_states(name
, my_id
, sym
, two_state
, one_state
);
519 case SPECIAL_UNSIGNED_GT
:
520 one_state
= filter_range(orig
, whole_range
.min
, value
);
521 two_state
= filter_range(orig
, value
+ 1, whole_range
.max
);
523 set_true_false_states(name
, my_id
, sym
, one_state
, two_state
);
525 set_true_false_states(name
, my_id
, sym
, two_state
, one_state
);
527 case SPECIAL_NOTEQUAL
:
528 one_state
= filter_range(orig
, value
, value
);
529 two_state
= filter_range(orig
, value
, value
);
530 set_true_false_states(name
, my_id
, sym
, two_state
, one_state
);
533 smatch_msg("unhandled comparison %d\n", comparison
);
541 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
542 void __extra_match_condition(struct expression
*expr
)
546 struct smatch_state
*pre_state
;
547 struct smatch_state
*true_state
;
548 struct smatch_state
*false_state
;
550 expr
= strip_expr(expr
);
555 name
= get_variable_from_expr(expr
, &sym
);
558 pre_state
= get_state(name
, my_id
, sym
);
559 true_state
= add_filter(pre_state
, 0);
560 false_state
= alloc_extra_state(0);
561 set_true_false_states(name
, my_id
, sym
, true_state
, false_state
);
565 match_comparison(expr
);
570 static int variable_non_zero(struct expression
*expr
)
574 struct smatch_state
*state
;
577 name
= get_variable_from_expr(expr
, &sym
);
580 state
= get_state(name
, my_id
, sym
);
581 if (!state
|| !state
->data
)
583 ret
= !possibly_false(SPECIAL_NOTEQUAL
, (struct data_info
*)state
->data
, 0, 1);
589 int known_condition_true(struct expression
*expr
)
596 tmp
= get_value(expr
);
597 if (tmp
&& tmp
!= UNDEFINED
)
600 expr
= strip_expr(expr
);
603 if (expr
->op
== '!') {
604 if (known_condition_false(expr
->unop
))
615 int known_condition_false(struct expression
*expr
)
625 if (expr
->op
== '!') {
626 if (known_condition_true(expr
->unop
))
637 static int do_comparison_range(struct expression
*expr
)
641 struct smatch_state
*state
;
644 int poss_true
, poss_false
;
646 value
= get_value(expr
->left
);
647 if (value
== UNDEFINED
) {
648 value
= get_value(expr
->right
);
649 if (value
== UNDEFINED
)
654 name
= get_variable_from_expr(expr
->left
, &sym
);
656 name
= get_variable_from_expr(expr
->right
, &sym
);
659 state
= get_state(name
, SMATCH_EXTRA
, sym
);
662 poss_true
= possibly_true(expr
->op
, (struct data_info
*)state
->data
, value
, left
);
663 poss_false
= possibly_false(expr
->op
, (struct data_info
*)state
->data
, value
, left
);
664 if (!poss_true
&& !poss_false
)
666 if (poss_true
&& !poss_false
)
668 if (!poss_true
&& poss_false
)
670 if (poss_true
&& poss_false
)
677 int implied_condition_true(struct expression
*expr
)
679 struct statement
*stmt
;
685 tmp
= get_value(expr
);
686 if (tmp
&& tmp
!= UNDEFINED
)
689 expr
= strip_expr(expr
);
692 if (do_comparison_range(expr
) == 1)
696 if (expr
->op
== '!') {
697 if (implied_condition_false(expr
->unop
))
701 stmt
= get_block_thing(expr
);
702 if (stmt
&& (last_stmt_val(stmt
) == 1))
706 if (variable_non_zero(expr
) == 1)
713 int implied_condition_false(struct expression
*expr
)
715 struct statement
*stmt
;
716 struct expression
*tmp
;
726 if (do_comparison_range(expr
) == 2)
729 if (expr
->op
== '!') {
730 if (implied_condition_true(expr
->unop
))
734 stmt
= get_block_thing(expr
);
735 if (stmt
&& (last_stmt_val(stmt
) == 0))
737 tmp
= strip_expr(expr
);
739 return implied_condition_false(tmp
);
742 if (variable_non_zero(expr
) == 0)
749 void register_smatch_extra(int id
)
752 add_merge_hook(my_id
, &merge_func
);
753 add_unmatched_state_hook(my_id
, &unmatched_state
);
754 add_hook(&undef_expr
, OP_HOOK
);
755 add_hook(&match_function_def
, FUNC_DEF_HOOK
);
756 add_hook(&match_function_call
, FUNCTION_CALL_HOOK
);
757 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
758 add_hook(&match_declarations
, DECLARATION_HOOK
);
759 add_hook(&match_unop
, OP_HOOK
);
760 add_hook(&free_data_info_allocs
, END_FUNC_HOOK
);
763 /* I don't know how to test for the ATTRIB_NORET attribute. :( */
764 add_function_hook("panic", &__match_nullify_path_hook
, NULL
);
765 add_function_hook("do_exit", &__match_nullify_path_hook
, NULL
);
766 add_function_hook("complete_and_exit", &__match_nullify_path_hook
, NULL
);
767 add_function_hook("__module_put_and_exit", &__match_nullify_path_hook
, NULL
);
768 add_function_hook("do_group_exit", &__match_nullify_path_hook
, NULL
);