dadf573eb0ed993219b354115faaf5f79c97084e
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.
23 #include "smatch_slist.h"
24 #include "smatch_extra.h"
28 struct string_list
*__ignored_macros
= NULL
;
29 static int in_warn_on_macro()
31 struct statement
*stmt
;
35 stmt
= get_current_statement();
36 macro
= get_macro_name(stmt
->pos
);
40 FOR_EACH_PTR(__ignored_macros
, tmp
) {
41 if (!strcmp(tmp
, macro
))
43 } END_FOR_EACH_PTR(tmp
);
47 typedef void (mod_hook
)(const char *name
, struct symbol
*sym
, struct smatch_state
*state
);
48 DECLARE_PTR_LIST(void_fn_list
, mod_hook
*);
49 static struct void_fn_list
*extra_mod_hooks
;
50 void add_extra_mod_hook(mod_hook
*fn
)
52 mod_hook
**p
= malloc(sizeof(mod_hook
*));
54 add_ptr_list(&extra_mod_hooks
, p
);
57 static void call_extra_mod_hooks(const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
61 FOR_EACH_PTR(extra_mod_hooks
, fn
) {
62 (*fn
)(name
, sym
, state
);
63 } END_FOR_EACH_PTR(fn
);
66 struct sm_state
*set_extra_mod(const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
68 if (in_warn_on_macro())
70 remove_from_equiv(name
, sym
);
71 call_extra_mod_hooks(name
, sym
, state
);
72 return set_state(SMATCH_EXTRA
, name
, sym
, state
);
75 struct sm_state
*set_extra_expr_mod(struct expression
*expr
, struct smatch_state
*state
)
79 struct sm_state
*ret
= NULL
;
81 expr
= strip_expr(expr
);
82 name
= get_variable_from_expr(expr
, &sym
);
85 ret
= set_extra_mod(name
, sym
, state
);
91 void set_extra_nomod(const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
94 struct smatch_state
*orig_state
;
96 orig_state
= get_state(SMATCH_EXTRA
, name
, sym
);
98 if (!estate_related(orig_state
)) {
99 set_state(SMATCH_EXTRA
, name
, sym
, state
);
103 set_related(state
, estate_related(orig_state
));
104 FOR_EACH_PTR(estate_related(orig_state
), rel
) {
105 if (option_debug_related
)
106 sm_msg("updating related %s to %s", rel
->name
, state
->name
);
107 set_state(SMATCH_EXTRA
, rel
->name
, rel
->sym
, state
);
108 } END_FOR_EACH_PTR(rel
);
112 * This is for return_implies_state() hooks which modify a SMATCH_EXTRA state
114 void set_extra_expr_nomod(struct expression
*expr
, struct smatch_state
*state
)
119 name
= get_variable_from_expr(expr
, &sym
);
122 set_extra_nomod(name
, sym
, state
);
128 static void set_extra_true_false(const char *name
, struct symbol
*sym
,
129 struct smatch_state
*true_state
,
130 struct smatch_state
*false_state
)
132 struct relation
*rel
;
133 struct smatch_state
*orig_state
;
135 if (in_warn_on_macro())
138 orig_state
= get_state(SMATCH_EXTRA
, name
, sym
);
140 if (!estate_related(orig_state
)) {
141 set_true_false_states(SMATCH_EXTRA
, name
, sym
, true_state
, false_state
);
146 set_related(true_state
, estate_related(orig_state
));
148 set_related(false_state
, estate_related(orig_state
));
150 FOR_EACH_PTR(estate_related(orig_state
), rel
) {
151 set_true_false_states(SMATCH_EXTRA
, rel
->name
, rel
->sym
,
152 true_state
, false_state
);
153 } END_FOR_EACH_PTR(rel
);
156 static void set_extra_expr_true_false(struct expression
*expr
,
157 struct smatch_state
*true_state
,
158 struct smatch_state
*false_state
)
163 expr
= strip_expr(expr
);
164 name
= get_variable_from_expr(expr
, &sym
);
167 set_extra_true_false(name
, sym
, true_state
, false_state
);
172 struct smatch_state
*filter_range(struct smatch_state
*orig
,
173 sval_t filter_min
, sval_t filter_max
)
175 struct range_list
*rl
;
178 orig
= extra_undefined(filter_min
.type
);
180 rl
= remove_range(estate_ranges(orig
), filter_min
, filter_max
);
181 return alloc_estate_range_list(rl
);
184 struct smatch_state
*add_filter(struct smatch_state
*orig
, sval_t sval
)
186 return filter_range(orig
, sval
, sval
);
189 static struct sm_state
*handle_canonical_while_count_down(struct statement
*loop
)
191 struct expression
*iter_var
;
192 struct expression
*condition
;
194 struct smatch_state
*estate
;
197 condition
= strip_expr(loop
->iterator_pre_condition
);
200 if (condition
->type
!= EXPR_PREOP
&& condition
->type
!= EXPR_POSTOP
)
202 if (condition
->op
!= SPECIAL_DECREMENT
)
205 iter_var
= condition
->unop
;
206 sm
= get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
209 if (sval_cmp_val(estate_min(sm
->state
), 0) < 0)
211 start
= estate_max(sm
->state
);
212 if (sval_cmp_val(start
, 0) <= 0)
214 if (!sval_is_max(start
))
217 if (condition
->type
== EXPR_PREOP
) {
218 estate
= alloc_estate_range(sval_type_val(start
.type
, 1), start
);
219 if (estate_has_hard_max(sm
->state
))
220 estate_set_hard_max(estate
);
221 set_extra_expr_mod(iter_var
, estate
);
223 if (condition
->type
== EXPR_POSTOP
) {
224 estate
= alloc_estate_range(sval_type_val(start
.type
, 0), start
);
225 if (estate_has_hard_max(sm
->state
))
226 estate_set_hard_max(estate
);
227 set_extra_expr_mod(iter_var
, estate
);
229 return get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
232 static struct sm_state
*handle_canonical_for_inc(struct expression
*iter_expr
,
233 struct expression
*condition
)
235 struct expression
*iter_var
;
237 struct smatch_state
*estate
;
238 sval_t start
, end
, dummy
;
240 iter_var
= iter_expr
->unop
;
241 sm
= get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
244 if (!estate_get_single_value(sm
->state
, &start
))
246 if (!get_implied_max(condition
->right
, &end
))
247 end
= sval_type_max(get_type(iter_var
));
249 if (get_sm_state_expr(SMATCH_EXTRA
, condition
->left
) != sm
)
252 switch (condition
->op
) {
253 case SPECIAL_NOTEQUAL
:
255 if (!sval_is_min(end
))
263 if (sval_cmp(end
, start
) < 0)
265 estate
= alloc_estate_range(start
, end
);
266 if (get_hard_max(condition
->right
, &dummy
))
267 estate_set_hard_max(estate
);
268 set_extra_expr_mod(iter_var
, estate
);
269 return get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
272 static struct sm_state
*handle_canonical_for_dec(struct expression
*iter_expr
,
273 struct expression
*condition
)
275 struct expression
*iter_var
;
277 struct smatch_state
*estate
;
280 iter_var
= iter_expr
->unop
;
281 sm
= get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
284 if (!estate_get_single_value(sm
->state
, &start
))
286 if (!get_implied_min(condition
->right
, &end
))
287 end
= sval_type_min(get_type(iter_var
));
288 if (get_sm_state_expr(SMATCH_EXTRA
, condition
->left
) != sm
)
291 switch (condition
->op
) {
292 case SPECIAL_NOTEQUAL
:
294 if (!sval_is_min(end
) && !sval_is_max(end
))
302 if (sval_cmp(end
, start
) > 0)
304 estate
= alloc_estate_range(end
, start
);
305 estate_set_hard_max(estate
);
306 set_extra_expr_mod(iter_var
, estate
);
307 return get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
310 static struct sm_state
*handle_canonical_for_loops(struct statement
*loop
)
312 struct expression
*iter_expr
;
313 struct expression
*condition
;
315 if (!loop
->iterator_post_statement
)
317 if (loop
->iterator_post_statement
->type
!= STMT_EXPRESSION
)
319 iter_expr
= loop
->iterator_post_statement
->expression
;
320 if (!loop
->iterator_pre_condition
)
322 if (loop
->iterator_pre_condition
->type
!= EXPR_COMPARE
)
324 condition
= loop
->iterator_pre_condition
;
326 if (iter_expr
->op
== SPECIAL_INCREMENT
)
327 return handle_canonical_for_inc(iter_expr
, condition
);
328 if (iter_expr
->op
== SPECIAL_DECREMENT
)
329 return handle_canonical_for_dec(iter_expr
, condition
);
333 struct sm_state
*__extra_handle_canonical_loops(struct statement
*loop
, struct state_list
**slist
)
335 struct sm_state
*ret
;
337 __push_fake_cur_slist();
338 if (!loop
->iterator_post_statement
)
339 ret
= handle_canonical_while_count_down(loop
);
341 ret
= handle_canonical_for_loops(loop
);
342 *slist
= __pop_fake_cur_slist();
346 int __iterator_unchanged(struct sm_state
*sm
)
350 if (get_sm_state(my_id
, sm
->name
, sm
->sym
) == sm
)
355 static void while_count_down_after(struct sm_state
*sm
, struct expression
*condition
)
359 /* paranoid checking. prolly not needed */
360 condition
= strip_expr(condition
);
363 if (condition
->type
!= EXPR_PREOP
&& condition
->type
!= EXPR_POSTOP
)
365 if (condition
->op
!= SPECIAL_DECREMENT
)
367 after_value
= estate_min(sm
->state
);
369 set_extra_mod(sm
->name
, sm
->sym
, alloc_estate_sval(after_value
));
372 void __extra_pre_loop_hook_after(struct sm_state
*sm
,
373 struct statement
*iterator
,
374 struct expression
*condition
)
376 struct expression
*iter_expr
;
378 struct smatch_state
*state
;
381 while_count_down_after(sm
, condition
);
385 iter_expr
= iterator
->expression
;
387 if (condition
->type
!= EXPR_COMPARE
)
389 if (iter_expr
->op
== SPECIAL_INCREMENT
) {
390 limit
= sval_binop(estate_max(sm
->state
), '+',
391 sval_type_val(estate_type(sm
->state
), 1));
393 limit
= sval_binop(estate_min(sm
->state
), '-',
394 sval_type_val(estate_type(sm
->state
), 1));
396 if (!estate_has_hard_max(sm
->state
) && !__has_breaks()) {
397 if (iter_expr
->op
== SPECIAL_INCREMENT
)
398 state
= alloc_estate_range(estate_min(sm
->state
), limit
);
400 state
= alloc_estate_range(limit
, estate_max(sm
->state
));
402 state
= alloc_estate_sval(limit
);
404 if (!estate_has_hard_max(sm
->state
))
405 estate_clear_hard_max(state
);
406 set_extra_mod(sm
->name
, sm
->sym
, state
);
409 static struct state_list
*unmatched_slist
;
410 static struct smatch_state
*unmatched_state(struct sm_state
*sm
)
412 struct smatch_state
*state
;
414 if (unmatched_slist
) {
415 state
= get_state_slist(unmatched_slist
, SMATCH_EXTRA
, sm
->name
, sm
->sym
);
419 return extra_undefined(estate_type(sm
->state
));
422 static void match_function_call(struct expression
*expr
)
424 struct expression
*arg
;
425 struct expression
*tmp
;
427 FOR_EACH_PTR(expr
->args
, arg
) {
428 tmp
= strip_expr(arg
);
429 if (tmp
->type
== EXPR_PREOP
&& tmp
->op
== '&') {
430 remove_from_equiv_expr(tmp
->unop
);
431 set_state_expr(SMATCH_EXTRA
, tmp
->unop
, extra_undefined(get_type(tmp
->unop
)));
433 } END_FOR_EACH_PTR(arg
);
436 static int types_equiv_or_pointer(struct symbol
*one
, struct symbol
*two
)
440 if (one
->type
== SYM_PTR
&& two
->type
== SYM_PTR
)
442 return types_equiv(one
, two
);
445 static void match_assign(struct expression
*expr
)
447 struct range_list
*rl
= NULL
;
448 struct expression
*left
;
449 struct expression
*right
;
450 struct symbol
*right_sym
;
451 char *right_name
= NULL
;
456 sval_t right_min
, right_max
;
459 if (is_condition(expr
->right
))
461 left
= strip_expr(expr
->left
);
462 name
= get_variable_from_expr(left
, &sym
);
465 right
= strip_parens(expr
->right
);
466 while (right
->type
== EXPR_ASSIGNMENT
&& right
->op
== '=')
467 right
= strip_parens(right
->left
);
469 if (expr
->op
== '=' && right
->type
== EXPR_CALL
)
470 goto free
; /* these are handled in smatch_function_hooks.c */
472 right_name
= get_variable_from_expr(right
, &right_sym
);
473 if (expr
->op
== '=' && right_name
&& right_sym
&&
474 types_equiv_or_pointer(get_type(expr
->left
), get_type(expr
->right
))) {
475 set_equiv(left
, right
);
479 right_min
= sval_type_min(get_type(expr
->right
));
480 right_max
= sval_type_max(get_type(expr
->right
));
482 known
= get_implied_value(right
, &value
);
485 struct smatch_state
*state
;
487 if (get_implied_rl(right
, &rl
)) {
488 rl
= cast_rl(get_type(expr
->left
), rl
);
489 state
= alloc_estate_range_list(rl
);
490 if (get_hard_max(right
, &tmp
))
491 estate_set_hard_max(state
);
493 rl
= alloc_whole_rl(get_type(right
));
494 rl
= cast_rl(get_type(expr
->left
), rl
);
495 state
= alloc_estate_range_list(rl
);
497 set_extra_mod(name
, sym
, state
);
500 case SPECIAL_ADD_ASSIGN
:
501 if (get_implied_min(left
, &tmp
)) {
503 right_min
= sval_binop(tmp
, '+', value
);
507 if (!inside_loop() && known
&& get_implied_max(left
, &tmp
))
508 right_max
= sval_binop(tmp
, '+', value
);
510 case SPECIAL_SUB_ASSIGN
:
511 if (get_implied_max(left
, &tmp
)) {
513 right_max
= sval_binop(tmp
, '-', value
);
517 if (!inside_loop() && known
&& get_implied_min(left
, &tmp
))
518 right_min
= sval_binop(tmp
, '-', value
);
521 if (!sval_is_min(right_min
) || !sval_is_max(right_max
))
522 rl
= cast_rl(get_type(expr
->left
), alloc_rl(right_min
, right_max
));
524 rl
= alloc_whole_rl(get_type(expr
->left
));
525 set_extra_mod(name
, sym
, alloc_estate_range_list(rl
));
527 free_string(right_name
);
531 static void reset_struct_members(struct sm_state
*sm
)
533 set_extra_mod(sm
->name
, sm
->sym
, extra_undefined(estate_type(sm
->state
)));
536 static struct smatch_state
*increment_state(struct smatch_state
*state
)
538 sval_t min
= estate_min(state
);
539 sval_t max
= estate_max(state
);
541 if (!estate_ranges(state
))
545 max
= sval_type_max(max
.type
);
547 if (!sval_is_min(min
) && !sval_is_max(min
))
549 if (!sval_is_min(max
) && !sval_is_max(max
))
551 return alloc_estate_range(min
, max
);
554 static struct smatch_state
*decrement_state(struct smatch_state
*state
)
556 sval_t min
= estate_min(state
);
557 sval_t max
= estate_max(state
);
559 if (!estate_ranges(state
))
563 min
= sval_type_min(min
.type
);
565 if (!sval_is_min(min
) && !sval_is_max(min
))
567 if (!sval_is_min(max
) && !sval_is_max(max
))
569 return alloc_estate_range(min
, max
);
572 static void unop_expr(struct expression
*expr
)
574 struct smatch_state
*state
;
576 if (expr
->smatch_flags
& Handled
)
580 case SPECIAL_INCREMENT
:
581 state
= get_state_expr(SMATCH_EXTRA
, expr
->unop
);
582 state
= increment_state(state
);
584 state
= extra_undefined(get_type(expr
));
585 set_extra_expr_mod(expr
->unop
, state
);
587 case SPECIAL_DECREMENT
:
588 state
= get_state_expr(SMATCH_EXTRA
, expr
->unop
);
589 state
= decrement_state(state
);
591 state
= extra_undefined(get_type(expr
));
592 set_extra_expr_mod(expr
->unop
, state
);
599 static void asm_expr(struct statement
*stmt
)
602 struct expression
*expr
;
605 FOR_EACH_PTR(stmt
->asm_outputs
, expr
) {
607 case 0: /* identifier */
608 case 1: /* constraint */
611 case 2: /* expression */
613 set_extra_expr_mod(expr
, extra_undefined(get_type(expr
)));
616 } END_FOR_EACH_PTR(expr
);
619 static void delete_state_tracker(struct tracker
*t
)
621 remove_from_equiv(t
->name
, t
->sym
);
622 delete_state(t
->owner
, t
->name
, t
->sym
);
625 static void scoped_state_extra(const char *name
, struct symbol
*sym
)
629 t
= alloc_tracker(SMATCH_EXTRA
, name
, sym
);
630 add_scope_hook((scope_hook
*)&delete_state_tracker
, t
);
633 static void match_declarations(struct symbol
*sym
)
638 name
= sym
->ident
->name
;
639 if (!sym
->initializer
) {
640 set_state(SMATCH_EXTRA
, name
, sym
, extra_undefined(get_real_base_type(sym
)));
641 scoped_state_extra(name
, sym
);
646 static void check_dereference(struct expression
*expr
)
648 set_extra_expr_nomod(expr
, alloc_estate_range(valid_ptr_min_sval
, valid_ptr_max_sval
));
651 static void match_dereferences(struct expression
*expr
)
653 if (expr
->type
!= EXPR_PREOP
)
655 check_dereference(expr
->unop
);
658 static void match_pointer_as_array(struct expression
*expr
)
662 check_dereference(expr
->unop
->left
);
665 static void set_param_dereferenced(struct expression
*arg
, char *unused
)
667 check_dereference(arg
);
670 static void match_function_def(struct symbol
*sym
)
674 FOR_EACH_PTR(sym
->ctype
.base_type
->arguments
, arg
) {
677 set_state(my_id
, arg
->ident
->name
, arg
, extra_undefined(get_real_base_type(arg
)));
678 } END_FOR_EACH_PTR(arg
);
681 static int match_func_comparison(struct expression
*expr
)
683 struct expression
*left
= strip_expr(expr
->left
);
684 struct expression
*right
= strip_expr(expr
->right
);
687 if (left
->type
== EXPR_CALL
) {
688 if (!get_implied_value(right
, &sval
))
690 function_comparison(expr
->op
, left
, sval
, 1);
694 if (right
->type
== EXPR_CALL
) {
695 if (!get_implied_value(left
, &sval
))
697 function_comparison(expr
->op
, right
, sval
, 0);
704 static sval_t
add_one(sval_t sval
)
710 static sval_t
sub_one(sval_t sval
)
716 static void match_comparison(struct expression
*expr
)
718 struct expression
*left
= strip_expr(expr
->left
);
719 struct expression
*right
= strip_expr(expr
->right
);
721 struct range_list
*left_orig
;
722 struct range_list
*left_true
;
723 struct range_list
*left_false
;
724 struct range_list
*right_orig
;
725 struct range_list
*right_true
;
726 struct range_list
*right_false
;
727 struct smatch_state
*left_true_state
;
728 struct smatch_state
*left_false_state
;
729 struct smatch_state
*right_true_state
;
730 struct smatch_state
*right_false_state
;
731 sval_t min
, max
, dummy
;
733 int right_postop
= 0;
735 if (match_func_comparison(expr
))
738 if (left
->op
== SPECIAL_INCREMENT
|| left
->op
== SPECIAL_DECREMENT
) {
739 if (left
->type
== EXPR_POSTOP
) {
740 left
->smatch_flags
|= Handled
;
741 left_postop
= left
->op
;
743 left
= strip_expr(left
->unop
);
745 while (left
->type
== EXPR_ASSIGNMENT
)
746 left
= strip_expr(left
->left
);
748 if (right
->op
== SPECIAL_INCREMENT
|| right
->op
== SPECIAL_DECREMENT
) {
749 if (right
->type
== EXPR_POSTOP
) {
750 right
->smatch_flags
|= Handled
;
751 right_postop
= right
->op
;
753 right
= strip_expr(right
->unop
);
756 type
= get_type(expr
);
760 if (get_implied_rl(left
, &left_orig
)) {
761 left_orig
= cast_rl(type
, left_orig
);
763 min
= sval_type_min(get_type(left
));
764 max
= sval_type_max(get_type(left
));
765 left_orig
= cast_rl(type
, alloc_rl(min
, max
));
768 if (get_implied_rl(right
, &right_orig
)) {
769 right_orig
= cast_rl(type
, right_orig
);
771 min
= sval_type_min(get_type(right
));
772 max
= sval_type_max(get_type(right
));
773 right_orig
= cast_rl(type
, alloc_rl(min
, max
));
775 min
= sval_type_min(type
);
776 max
= sval_type_max(type
);
778 left_true
= clone_rl(left_orig
);
779 left_false
= clone_rl(left_orig
);
780 right_true
= clone_rl(right_orig
);
781 right_false
= clone_rl(right_orig
);
785 case SPECIAL_UNSIGNED_LT
:
786 left_true
= remove_range(left_orig
, rl_max(right_orig
), max
);
787 if (!sval_is_min(rl_min(right_orig
))) {
788 left_false
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
791 right_true
= remove_range(right_orig
, min
, rl_min(left_orig
));
792 if (!sval_is_max(rl_max(left_orig
)))
793 right_false
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
795 case SPECIAL_UNSIGNED_LTE
:
797 if (!sval_is_max(rl_max(right_orig
)))
798 left_true
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
799 left_false
= remove_range(left_orig
, min
, rl_min(right_orig
));
801 if (!sval_is_min(rl_min(left_orig
)))
802 right_true
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
803 right_false
= remove_range(right_orig
, rl_max(left_orig
), max
);
805 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
806 left_false
= remove_range(left_false
, rl_min(left_orig
), rl_min(left_orig
));
807 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
808 right_false
= remove_range(right_false
, rl_max(left_orig
), rl_max(left_orig
));
811 if (!sval_is_max(rl_max(right_orig
))) {
812 left_true
= remove_range(left_true
, add_one(rl_max(right_orig
)), max
);
814 if (!sval_is_min(rl_min(right_orig
))) {
815 left_true
= remove_range(left_true
, min
, sub_one(rl_min(right_orig
)));
817 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
818 left_false
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
820 if (!sval_is_max(rl_max(left_orig
)))
821 right_true
= remove_range(right_true
, add_one(rl_max(left_orig
)), max
);
822 if (!sval_is_min(rl_min(left_orig
)))
823 right_true
= remove_range(right_true
, min
, sub_one(rl_min(left_orig
)));
824 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
825 right_false
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
827 case SPECIAL_UNSIGNED_GTE
:
829 if (!sval_is_min(rl_min(right_orig
)))
830 left_true
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
831 left_false
= remove_range(left_orig
, rl_max(right_orig
), max
);
833 if (!sval_is_max(rl_max(left_orig
)))
834 right_true
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
835 right_false
= remove_range(right_orig
, min
, rl_min(left_orig
));
837 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
838 right_false
= remove_range(right_false
, rl_min(left_orig
), rl_min(left_orig
));
839 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
840 left_false
= remove_range(left_false
, rl_max(left_orig
), rl_max(left_orig
));
843 case SPECIAL_UNSIGNED_GT
:
844 left_true
= remove_range(left_orig
, min
, rl_min(right_orig
));
845 if (!sval_is_max(rl_max(right_orig
)))
846 left_false
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
848 right_true
= remove_range(right_orig
, rl_max(left_orig
), max
);
849 if (!sval_is_min(rl_min(left_orig
)))
850 right_false
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
852 case SPECIAL_NOTEQUAL
:
853 if (!sval_is_max(rl_max(right_orig
)))
854 left_false
= remove_range(left_false
, add_one(rl_max(right_orig
)), max
);
855 if (!sval_is_min(rl_min(right_orig
)))
856 left_false
= remove_range(left_false
, min
, sub_one(rl_min(right_orig
)));
857 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
858 left_true
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
860 if (!sval_is_max(rl_max(left_orig
)))
861 right_false
= remove_range(right_false
, add_one(rl_max(left_orig
)), max
);
862 if (!sval_is_min(rl_min(left_orig
)))
863 right_false
= remove_range(right_false
, min
, sub_one(rl_min(left_orig
)));
864 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
865 right_true
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
871 left_true_state
= alloc_estate_range_list(cast_rl(get_type(left
), left_true
));
872 left_false_state
= alloc_estate_range_list(cast_rl(get_type(left
), left_false
));
873 right_true_state
= alloc_estate_range_list(cast_rl(get_type(right
), right_true
));
874 right_false_state
= alloc_estate_range_list(cast_rl(get_type(right
), right_false
));
878 case SPECIAL_UNSIGNED_LT
:
879 case SPECIAL_UNSIGNED_LTE
:
881 if (get_hard_max(right
, &dummy
))
882 estate_set_hard_max(left_true_state
);
883 if (get_hard_max(left
, &dummy
))
884 estate_set_hard_max(right_false_state
);
887 case SPECIAL_UNSIGNED_GT
:
888 case SPECIAL_UNSIGNED_GTE
:
890 if (get_hard_max(left
, &dummy
))
891 estate_set_hard_max(right_true_state
);
892 if (get_hard_max(right
, &dummy
))
893 estate_set_hard_max(left_false_state
);
897 if (get_hard_max(left
, &dummy
)) {
898 estate_set_hard_max(left_true_state
);
899 estate_set_hard_max(left_false_state
);
901 if (get_hard_max(right
, &dummy
)) {
902 estate_set_hard_max(right_true_state
);
903 estate_set_hard_max(right_false_state
);
906 if (left_postop
== SPECIAL_INCREMENT
) {
907 left_true_state
= increment_state(left_true_state
);
908 left_false_state
= increment_state(left_false_state
);
910 if (left_postop
== SPECIAL_DECREMENT
) {
911 left_true_state
= decrement_state(left_true_state
);
912 left_false_state
= decrement_state(left_false_state
);
914 if (right_postop
== SPECIAL_INCREMENT
) {
915 right_true_state
= increment_state(right_true_state
);
916 right_false_state
= increment_state(right_false_state
);
918 if (right_postop
== SPECIAL_DECREMENT
) {
919 right_true_state
= decrement_state(right_true_state
);
920 right_false_state
= decrement_state(right_false_state
);
923 set_extra_expr_true_false(left
, left_true_state
, left_false_state
);
924 set_extra_expr_true_false(right
, right_true_state
, right_false_state
);
927 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
928 void __extra_match_condition(struct expression
*expr
)
932 struct smatch_state
*pre_state
;
933 struct smatch_state
*true_state
;
934 struct smatch_state
*false_state
;
936 expr
= strip_expr(expr
);
937 switch (expr
->type
) {
939 function_comparison(SPECIAL_NOTEQUAL
, expr
, ll_to_sval(0), 1);
946 zero
= sval_blank(expr
);
949 name
= get_variable_from_expr(expr
, &sym
);
952 pre_state
= get_state(my_id
, name
, sym
);
953 true_state
= add_filter(pre_state
, zero
);
954 if (possibly_true(expr
, SPECIAL_EQUAL
, zero_expr()))
955 false_state
= alloc_estate_sval(zero
);
957 false_state
= alloc_estate_empty();
958 set_extra_true_false(name
, sym
, true_state
, false_state
);
963 match_comparison(expr
);
965 case EXPR_ASSIGNMENT
:
966 __extra_match_condition(expr
->left
);
971 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
972 int implied_not_equal(struct expression
*expr
, long long val
)
974 return !possibly_false(expr
, SPECIAL_NOTEQUAL
, value_expr(val
));
977 int is_whole_range(struct smatch_state
*state
)
979 return is_whole_rl(estate_ranges(state
));
982 static void struct_member_callback(char *fn
, char *global_static
, int param
, char *printed_name
, struct smatch_state
*state
)
984 if (is_whole_range(state
))
986 sm_msg("info: passes param_value '%s' %d '%s' %s %s", fn
, param
, printed_name
, state
->name
, global_static
);
989 static void db_limited_before(void)
991 unmatched_slist
= clone_slist(__get_cur_slist());
994 static void db_limited_after(void)
996 free_slist(&unmatched_slist
);
999 static char *get_variable_from_key(struct expression
*arg
, char *key
, struct symbol
**sym
)
1004 if (strcmp(key
, "$$") == 0)
1005 return get_variable_from_expr(arg
, sym
);
1007 if (strcmp(key
, "*$$") == 0) {
1008 if (arg
->type
== EXPR_PREOP
&& arg
->op
== '&') {
1009 arg
= strip_expr(arg
->unop
);
1010 return get_variable_from_expr(arg
, sym
);
1012 tmp
= get_variable_from_expr(arg
, sym
);
1015 snprintf(buf
, sizeof(buf
), "*%s", tmp
);
1017 return alloc_string(buf
);
1021 if (arg
->type
== EXPR_PREOP
&& arg
->op
== '&') {
1022 arg
= strip_expr(arg
->unop
);
1023 tmp
= get_variable_from_expr(arg
, sym
);
1026 snprintf(buf
, sizeof(buf
), "%s.%s", tmp
, key
+ 4);
1027 return alloc_string(buf
);
1030 tmp
= get_variable_from_expr(arg
, sym
);
1033 snprintf(buf
, sizeof(buf
), "%s%s", tmp
, key
+ 2);
1035 return alloc_string(buf
);
1038 static void db_param_limit_filter(struct expression
*expr
, int param
, char *key
, char *value
)
1040 struct expression
*arg
;
1043 struct sm_state
*sm
;
1044 struct symbol
*type
;
1045 struct range_list
*rl
;
1046 struct range_list
*limit
;
1047 struct range_list
*new;
1049 while (expr
->type
== EXPR_ASSIGNMENT
)
1050 expr
= strip_expr(expr
->right
);
1051 if (expr
->type
!= EXPR_CALL
)
1054 arg
= get_argument_from_call_expr(expr
->args
, param
);
1058 name
= get_variable_from_key(arg
, key
, &sym
);
1062 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
1063 type
= get_member_type_from_key(arg
, key
);
1065 rl
= estate_ranges(sm
->state
);
1067 rl
= alloc_whole_rl(type
);
1069 str_to_rl(type
, value
, &limit
);
1070 new = rl_intersection(rl
, limit
);
1072 /* We want to preserve the implications here */
1073 if (sm
&& rl_equiv(estate_ranges(sm
->state
), new))
1076 set_extra_nomod(name
, sym
, alloc_estate_range_list(new));
1082 static void db_param_add(struct expression
*expr
, int param
, char *key
, char *value
)
1084 struct expression
*arg
;
1087 struct symbol
*type
;
1088 struct smatch_state
*state
;
1089 struct range_list
*added
= NULL
;
1090 struct range_list
*new;
1092 while (expr
->type
== EXPR_ASSIGNMENT
)
1093 expr
= strip_expr(expr
->right
);
1094 if (expr
->type
!= EXPR_CALL
)
1097 arg
= get_argument_from_call_expr(expr
->args
, param
);
1100 name
= get_variable_from_key(arg
, key
, &sym
);
1104 type
= get_member_type_from_key(arg
, key
);
1105 state
= get_state(SMATCH_EXTRA
, name
, sym
);
1107 str_to_rl(type
, value
, &added
);
1108 new = rl_union(estate_ranges(state
), added
);
1110 new = alloc_whole_rl(type
);
1113 set_extra_mod(name
, sym
, alloc_estate_range_list(new));
1118 static void db_returned_states_param(struct expression
*expr
, int param
, char *key
, char *value
)
1120 struct expression
*arg
;
1121 struct symbol
*type
;
1122 struct range_list
*rl
;
1123 char member_name
[256];
1127 while (expr
->type
== EXPR_ASSIGNMENT
)
1128 expr
= strip_expr(expr
->right
);
1129 if (expr
->type
!= EXPR_CALL
)
1131 arg
= get_argument_from_call_expr(expr
->args
, param
);
1132 arg
= strip_expr(arg
);
1136 if (strcmp(key
, "*$$") == 0) {
1141 if (arg
->type
== EXPR_PREOP
&& arg
->op
== '&') {
1142 arg
= strip_expr(arg
->unop
);
1143 name
= get_variable_from_expr(arg
, &sym
);
1145 char *tmp
= get_variable_from_expr(arg
, &sym
);
1149 snprintf(buf
, sizeof(buf
), "*%s", tmp
);
1150 name
= alloc_string(buf
);
1153 if (!name
|| !sym
) {
1157 type
= get_type(arg
);
1158 str_to_rl(type
, value
, &rl
);
1159 set_extra_mod(name
, sym
, alloc_estate_range_list(rl
));
1164 if (arg
->type
== EXPR_PREOP
&& arg
->op
== '&') {
1165 arg
= strip_expr(arg
->unop
);
1166 name
= get_variable_from_expr(arg
, &sym
);
1169 snprintf(member_name
, sizeof(member_name
), "%s.%s", name
, key
+ 4);
1171 name
= get_variable_from_expr(arg
, &sym
);
1174 snprintf(member_name
, sizeof(member_name
), "%s%s", name
, key
+ 2);
1176 type
= get_member_type_from_key(arg
, key
);
1179 str_to_rl(type
, value
, &rl
);
1180 set_extra_mod(member_name
, sym
, alloc_estate_range_list(rl
));
1185 static void db_returned_member_info(struct expression
*expr
, int param
, char *key
, char *value
)
1187 struct symbol
*type
;
1190 char member_name
[256];
1191 struct range_list
*rl
;
1193 if (expr
->type
!= EXPR_ASSIGNMENT
)
1196 name
= get_variable_from_expr(expr
->left
, &sym
);
1199 snprintf(member_name
, sizeof(member_name
), "%s%s", name
, key
+ 2);
1200 type
= get_member_type_from_key(expr
->left
, key
);
1203 str_to_rl(type
, value
, &rl
);
1204 set_extra_mod(member_name
, sym
, alloc_estate_range_list(rl
));
1210 static void returned_member_callback(int return_id
, char *return_ranges
, char *printed_name
, struct smatch_state
*state
)
1212 if (is_whole_range(state
))
1214 sm_msg("info: return_value %d '%s' '%s' '%s' %s", return_id
,
1215 return_ranges
, printed_name
, state
->name
, global_static());
1218 static void match_call_info(struct expression
*expr
)
1220 struct range_list
*rl
= NULL
;
1221 struct expression
*arg
;
1222 struct symbol
*type
;
1226 name
= get_fnptr_name(expr
->fn
);
1230 FOR_EACH_PTR(expr
->args
, arg
) {
1231 type
= get_arg_type(expr
->fn
, i
);
1233 if (get_implied_rl(arg
, &rl
))
1234 rl
= cast_rl(type
, rl
);
1236 rl
= alloc_whole_rl(type
);
1238 sm_msg("info: passes param_value '%s' %d '$$' %s %s",
1239 name
, i
, show_ranges(rl
),
1240 is_static(expr
->fn
) ? "static" : "global");
1242 } END_FOR_EACH_PTR(arg
);
1247 static void set_param_value(const char *name
, struct symbol
*sym
, char *key
, char *value
)
1249 struct range_list
*rl
= NULL
;
1250 struct smatch_state
*state
;
1251 struct symbol
*type
;
1254 if (strncmp(key
, "$$", 2))
1257 snprintf(fullname
, 256, "%s%s", name
, key
+ 2);
1258 type
= get_member_type_from_key(symbol_expression(sym
), key
);
1259 str_to_rl(type
, value
, &rl
);
1260 state
= alloc_estate_range_list(rl
);
1261 set_state(SMATCH_EXTRA
, fullname
, sym
, state
);
1264 void register_smatch_extra(int id
)
1268 add_merge_hook(my_id
, &merge_estates
);
1269 add_unmatched_state_hook(my_id
, &unmatched_state
);
1270 add_hook(&match_function_def
, FUNC_DEF_HOOK
);
1271 add_hook(&match_declarations
, DECLARATION_HOOK
);
1272 add_definition_db_callback(set_param_value
, PARAM_VALUE
);
1273 add_db_return_states_callback(RETURN_VALUE
, &db_returned_member_info
);
1274 add_db_return_states_callback(PARAM_VALUE
, &db_returned_states_param
);
1275 add_db_return_states_before(&db_limited_before
);
1276 add_db_return_states_callback(LIMITED_VALUE
, &db_param_limit_filter
);
1277 add_db_return_states_callback(FILTER_VALUE
, &db_param_limit_filter
);
1278 add_db_return_states_callback(ADDED_VALUE
, &db_param_add
);
1279 add_db_return_states_after(&db_limited_after
);
1282 void register_smatch_extra_late(int id
)
1284 add_hook(&match_dereferences
, DEREF_HOOK
);
1285 add_hook(&match_pointer_as_array
, OP_HOOK
);
1286 add_db_fn_call_callback(DEREFERENCE
, &set_param_dereferenced
);
1287 add_indirect_modification_hook(SMATCH_EXTRA
, reset_struct_members
);
1289 add_hook(&match_function_call
, FUNCTION_CALL_HOOK
);
1290 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
1291 add_hook(&unop_expr
, OP_HOOK
);
1292 add_hook(&asm_expr
, ASM_HOOK
);
1295 add_hook(&match_call_info
, FUNCTION_CALL_HOOK
);
1296 add_member_info_callback(my_id
, struct_member_callback
);
1297 add_returned_member_callback(my_id
, returned_member_callback
);