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";
71 struct smatch_state
*alloc_extra_state(int val
)
73 struct smatch_state
*state
;
76 return extra_undefined();
77 state
= alloc_extra_state_no_name(val
);
78 state
->name
= show_ranges(((struct data_info
*)state
->data
)->value_ranges
);
82 struct smatch_state
*alloc_extra_state_range(long long min
, long long max
)
84 struct smatch_state
*state
;
86 state
= __alloc_smatch_state(0);
87 state
->data
= (void *)alloc_dinfo_range(min
, max
);
88 state
->name
= show_ranges(((struct data_info
*)state
->data
)->value_ranges
);
92 struct smatch_state
*filter_range(struct smatch_state
*orig
,
93 long long filter_min
, long long filter_max
)
95 struct smatch_state
*ret
;
96 struct data_info
*orig_info
;
97 struct data_info
*ret_info
;
100 orig
= extra_undefined();
101 orig_info
= (struct data_info
*)orig
->data
;
102 ret
= alloc_extra_state_empty();
103 ret_info
= (struct data_info
*)ret
->data
;
104 ret_info
->value_ranges
= remove_range(orig_info
->value_ranges
, filter_min
, filter_max
);
105 ret
->name
= show_ranges(ret_info
->value_ranges
);
109 struct smatch_state
*add_filter(struct smatch_state
*orig
, long long num
)
111 return filter_range(orig
, num
, num
);
114 static struct smatch_state
*merge_func(const char *name
, struct symbol
*sym
,
115 struct smatch_state
*s1
,
116 struct smatch_state
*s2
)
118 struct data_info
*info1
= (struct data_info
*)s1
->data
;
119 struct data_info
*info2
= (struct data_info
*)s2
->data
;
120 struct data_info
*ret_info
;
121 struct smatch_state
*tmp
;
123 tmp
= alloc_extra_state_empty();
124 tmp
->name
= "extra_merged";
125 ret_info
= (struct data_info
*)tmp
->data
;
126 ret_info
->merged
= 1;
127 ret_info
->value_ranges
= range_list_union(info1
->value_ranges
, info2
->value_ranges
);
131 struct sm_state
*__extra_merge(struct sm_state
*one
, struct state_list
*slist1
,
132 struct sm_state
*two
, struct state_list
*slist2
)
134 struct data_info
*info1
;
135 struct data_info
*info2
;
137 if (!one
->state
->data
|| !two
->state
->data
) {
138 smatch_msg("internal error in smatch extra '%s = %s or %s'",
139 one
->name
, show_state(one
->state
),
140 show_state(two
->state
));
141 return alloc_state(one
->name
, one
->owner
, one
->sym
,
145 info1
= (struct data_info
*)one
->state
->data
;
146 info2
= (struct data_info
*)two
->state
->data
;
149 free_stack(&one
->my_pools
);
151 free_stack(&two
->my_pools
);
153 if (one
== two
&& !one
->my_pools
) {
154 add_pool(&one
->my_pools
, slist1
);
155 add_pool(&one
->my_pools
, slist2
);
158 add_pool(&one
->my_pools
, slist1
);
160 add_pool(&two
->my_pools
, slist2
);
163 add_pool(&one
->all_pools
, slist1
);
164 add_pool(&two
->all_pools
, slist2
);
165 return merge_sm_states(one
, two
);
168 struct sm_state
*__extra_and_merge(struct sm_state
*sm
,
169 struct state_list_stack
*stack
)
171 struct state_list
*slist
;
172 struct sm_state
*ret
= NULL
;
173 struct sm_state
*tmp
;
176 FOR_EACH_PTR(stack
, slist
) {
178 ret
= get_sm_state_slist(slist
, sm
->name
, sm
->owner
,
181 tmp
= get_sm_state_slist(slist
, sm
->name
, sm
->owner
,
183 ret
= merge_sm_states(ret
, tmp
);
185 } END_FOR_EACH_PTR(slist
);
187 smatch_msg("Internal error in __extra_and_merge");
190 ret
->my_pools
= stack
;
191 ret
->all_pools
= clone_stack(stack
);
195 static struct smatch_state
*unmatched_state(struct sm_state
*sm
)
197 return extra_undefined();
200 static void match_function_call(struct expression
*expr
)
202 struct expression
*tmp
;
207 FOR_EACH_PTR(expr
->args
, tmp
) {
208 if (tmp
->op
== '&') {
209 name
= get_variable_from_expr(tmp
->unop
, &sym
);
211 set_state(name
, my_id
, sym
, extra_undefined());
216 } END_FOR_EACH_PTR(tmp
);
219 static void match_assign(struct expression
*expr
)
221 struct expression
*left
;
225 left
= strip_expr(expr
->left
);
226 name
= get_variable_from_expr(left
, &sym
);
229 set_state(name
, my_id
, sym
, alloc_extra_state(get_value(expr
->right
)));
233 static void undef_expr(struct expression
*expr
)
238 name
= get_variable_from_expr(expr
->unop
, &sym
);
241 if (!get_state(name
, my_id
, sym
)) {
245 set_state(name
, my_id
, sym
, extra_undefined());
249 static void match_declarations(struct symbol
*sym
)
254 name
= sym
->ident
->name
;
255 if (sym
->initializer
) {
256 set_state(name
, my_id
, sym
, alloc_extra_state(get_value(sym
->initializer
)));
258 set_state(name
, my_id
, sym
, extra_undefined());
263 static void match_function_def(struct symbol
*sym
)
268 FOR_EACH_PTR(sym
->ctype
.base_type
->arguments
, arg
) {
272 set_state(arg
->ident
->name
, my_id
, arg
, extra_undefined());
273 } END_FOR_EACH_PTR(arg
);
276 static void match_unop(struct expression
*expr
)
283 name
= get_variable_from_expr(expr
->unop
, &sym
);
287 tmp
= show_special(expr
->op
);
288 if ((!strcmp(tmp
, "--")) || (!strcmp(tmp
, "++")))
289 set_state(name
, my_id
, sym
, extra_undefined());
293 int get_implied_value(struct expression
*expr
)
295 struct smatch_state
*state
;
300 val
= get_value(expr
);
301 if (val
!= UNDEFINED
)
304 name
= get_variable_from_expr(expr
, &sym
);
307 state
= get_state(name
, my_id
, sym
);
309 if (!state
|| !state
->data
)
311 return get_single_value_from_range((struct data_info
*)state
->data
);
314 int last_stmt_val(struct statement
*stmt
)
316 struct expression
*expr
;
318 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
319 if (stmt
->type
!= STMT_EXPRESSION
)
321 expr
= stmt
->expression
;
322 return get_value(expr
);
325 static void match_comparison(struct expression
*expr
)
330 struct smatch_state
*one_state
;
331 struct smatch_state
*two_state
;
332 struct smatch_state
*orig
;
334 int comparison
= expr
->op
;
336 value
= get_value(expr
->left
);
337 if (value
== UNDEFINED
) {
338 value
= get_value(expr
->right
);
339 if (value
== UNDEFINED
)
344 name
= get_variable_from_expr(expr
->left
, &sym
);
346 name
= get_variable_from_expr(expr
->right
, &sym
);
350 orig
= get_state(name
, my_id
, sym
);
352 orig
= extra_undefined();
356 case SPECIAL_UNSIGNED_LT
:
357 one_state
= filter_range(orig
, whole_range
.min
, value
- 1);
358 two_state
= filter_range(orig
, value
, whole_range
.max
);
360 set_true_false_states(name
, my_id
, sym
, two_state
, one_state
);
362 set_true_false_states(name
, my_id
, sym
, one_state
, two_state
);
364 case SPECIAL_UNSIGNED_LTE
:
366 one_state
= filter_range(orig
, whole_range
.min
, value
);
367 two_state
= filter_range(orig
, value
+ 1, whole_range
.max
);
369 set_true_false_states(name
, my_id
, sym
, two_state
, one_state
);
371 set_true_false_states(name
, my_id
, sym
, one_state
, two_state
);
374 // todo. print a warning here for impossible conditions.
375 one_state
= alloc_extra_state(value
);
376 two_state
= filter_range(orig
, value
, value
);
377 set_true_false_states(name
, my_id
, sym
, one_state
, two_state
);
379 case SPECIAL_UNSIGNED_GTE
:
381 one_state
= filter_range(orig
, whole_range
.min
, value
- 1);
382 two_state
= filter_range(orig
, value
, whole_range
.max
);
384 set_true_false_states(name
, my_id
, sym
, one_state
, two_state
);
386 set_true_false_states(name
, my_id
, sym
, two_state
, one_state
);
389 case SPECIAL_UNSIGNED_GT
:
390 one_state
= filter_range(orig
, whole_range
.min
, value
);
391 two_state
= filter_range(orig
, value
+ 1, whole_range
.max
);
393 set_true_false_states(name
, my_id
, sym
, one_state
, two_state
);
395 set_true_false_states(name
, my_id
, sym
, two_state
, one_state
);
397 case SPECIAL_NOTEQUAL
:
398 one_state
= filter_range(orig
, value
, value
);
399 two_state
= filter_range(orig
, value
, value
);
400 set_true_false_states(name
, my_id
, sym
, two_state
, one_state
);
403 smatch_msg("unhandled comparison %d\n", comparison
);
411 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
412 void __extra_match_condition(struct expression
*expr
)
416 struct smatch_state
*pre_state
;
417 struct smatch_state
*true_state
;
418 struct smatch_state
*false_state
;
420 expr
= strip_expr(expr
);
425 name
= get_variable_from_expr(expr
, &sym
);
428 pre_state
= get_state(name
, my_id
, sym
);
429 true_state
= add_filter(pre_state
, 0);
430 false_state
= alloc_extra_state(0);
431 set_true_false_states(name
, my_id
, sym
, true_state
, false_state
);
435 match_comparison(expr
);
440 static int variable_non_zero(struct expression
*expr
)
444 struct smatch_state
*state
;
447 name
= get_variable_from_expr(expr
, &sym
);
450 state
= get_state(name
, my_id
, sym
);
451 if (!state
|| !state
->data
)
453 ret
= !possibly_false(SPECIAL_NOTEQUAL
, (struct data_info
*)state
->data
, 0, 1);
459 int known_condition_true(struct expression
*expr
)
466 tmp
= get_value(expr
);
467 if (tmp
&& tmp
!= UNDEFINED
)
470 expr
= strip_expr(expr
);
473 if (expr
->op
== '!') {
474 if (known_condition_false(expr
->unop
))
485 int known_condition_false(struct expression
*expr
)
495 if (expr
->op
== '!') {
496 if (known_condition_true(expr
->unop
))
507 static int do_comparison_range(struct expression
*expr
)
511 struct smatch_state
*state
;
514 int poss_true
, poss_false
;
516 value
= get_value(expr
->left
);
517 if (value
== UNDEFINED
) {
518 value
= get_value(expr
->right
);
519 if (value
== UNDEFINED
)
524 name
= get_variable_from_expr(expr
->left
, &sym
);
526 name
= get_variable_from_expr(expr
->right
, &sym
);
529 state
= get_state(name
, SMATCH_EXTRA
, sym
);
532 poss_true
= possibly_true(expr
->op
, (struct data_info
*)state
->data
, value
, left
);
533 poss_false
= possibly_false(expr
->op
, (struct data_info
*)state
->data
, value
, left
);
534 if (!poss_true
&& !poss_false
)
536 if (poss_true
&& !poss_false
)
538 if (!poss_true
&& poss_false
)
540 if (poss_true
&& poss_false
)
547 int implied_condition_true(struct expression
*expr
)
549 struct statement
*stmt
;
555 tmp
= get_value(expr
);
556 if (tmp
&& tmp
!= UNDEFINED
)
559 expr
= strip_expr(expr
);
562 if (do_comparison_range(expr
) == 1)
566 if (expr
->op
== '!') {
567 if (implied_condition_false(expr
->unop
))
571 stmt
= get_block_thing(expr
);
572 if (stmt
&& (last_stmt_val(stmt
) == 1))
576 if (variable_non_zero(expr
) == 1)
583 int implied_condition_false(struct expression
*expr
)
585 struct statement
*stmt
;
586 struct expression
*tmp
;
596 if (do_comparison_range(expr
) == 2)
599 if (expr
->op
== '!') {
600 if (implied_condition_true(expr
->unop
))
604 stmt
= get_block_thing(expr
);
605 if (stmt
&& (last_stmt_val(stmt
) == 0))
607 tmp
= strip_expr(expr
);
609 return implied_condition_false(tmp
);
612 if (variable_non_zero(expr
) == 0)
619 void register_smatch_extra(int id
)
622 add_merge_hook(my_id
, &merge_func
);
623 add_unmatched_state_hook(my_id
, &unmatched_state
);
624 add_hook(&undef_expr
, OP_HOOK
);
625 add_hook(&match_function_def
, FUNC_DEF_HOOK
);
626 add_hook(&match_function_call
, FUNCTION_CALL_HOOK
);
627 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
628 add_hook(&match_declarations
, DECLARATION_HOOK
);
629 add_hook(&match_unop
, OP_HOOK
);
630 add_hook(&free_data_info_allocs
, END_FUNC_HOOK
);
633 /* I don't know how to test for the ATTRIB_NORET attribute. :( */
634 add_function_hook("panic", &__match_nullify_path_hook
, NULL
);
635 add_function_hook("do_exit", &__match_nullify_path_hook
, NULL
);
636 add_function_hook("complete_and_exit", &__match_nullify_path_hook
, NULL
);
637 add_function_hook("__module_put_and_exit", &__match_nullify_path_hook
, NULL
);
638 add_function_hook("do_group_exit", &__match_nullify_path_hook
, NULL
);