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 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
= expr_to_var_sym(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
= expr_to_var_sym(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
= expr_to_var_sym(expr
, &sym
);
167 set_extra_true_false(name
, sym
, true_state
, false_state
);
172 static struct sm_state
*handle_canonical_while_count_down(struct statement
*loop
)
174 struct expression
*iter_var
;
175 struct expression
*condition
;
177 struct smatch_state
*estate
;
180 condition
= strip_expr(loop
->iterator_pre_condition
);
183 if (condition
->type
!= EXPR_PREOP
&& condition
->type
!= EXPR_POSTOP
)
185 if (condition
->op
!= SPECIAL_DECREMENT
)
188 iter_var
= condition
->unop
;
189 sm
= get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
192 if (sval_cmp_val(estate_min(sm
->state
), 0) < 0)
194 start
= estate_max(sm
->state
);
195 if (sval_cmp_val(start
, 0) <= 0)
197 if (!sval_is_max(start
))
200 if (condition
->type
== EXPR_PREOP
) {
201 estate
= alloc_estate_range(sval_type_val(start
.type
, 1), start
);
202 if (estate_has_hard_max(sm
->state
))
203 estate_set_hard_max(estate
);
204 set_extra_expr_mod(iter_var
, estate
);
206 if (condition
->type
== EXPR_POSTOP
) {
207 estate
= alloc_estate_range(sval_type_val(start
.type
, 0), start
);
208 if (estate_has_hard_max(sm
->state
))
209 estate_set_hard_max(estate
);
210 set_extra_expr_mod(iter_var
, estate
);
212 return get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
215 static struct sm_state
*handle_canonical_for_inc(struct expression
*iter_expr
,
216 struct expression
*condition
)
218 struct expression
*iter_var
;
220 struct smatch_state
*estate
;
221 sval_t start
, end
, dummy
;
223 iter_var
= iter_expr
->unop
;
224 sm
= get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
227 if (!estate_get_single_value(sm
->state
, &start
))
229 if (get_implied_max(condition
->right
, &end
))
230 end
= sval_cast(get_type(iter_var
), end
);
232 end
= sval_type_max(get_type(iter_var
));
234 if (get_sm_state_expr(SMATCH_EXTRA
, condition
->left
) != sm
)
237 switch (condition
->op
) {
238 case SPECIAL_NOTEQUAL
:
240 if (!sval_is_min(end
))
248 if (sval_cmp(end
, start
) < 0)
250 estate
= alloc_estate_range(start
, end
);
251 if (get_hard_max(condition
->right
, &dummy
))
252 estate_set_hard_max(estate
);
253 set_extra_expr_mod(iter_var
, estate
);
254 return get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
257 static struct sm_state
*handle_canonical_for_dec(struct expression
*iter_expr
,
258 struct expression
*condition
)
260 struct expression
*iter_var
;
262 struct smatch_state
*estate
;
265 iter_var
= iter_expr
->unop
;
266 sm
= get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
269 if (!estate_get_single_value(sm
->state
, &start
))
271 if (!get_implied_min(condition
->right
, &end
))
272 end
= sval_type_min(get_type(iter_var
));
273 if (get_sm_state_expr(SMATCH_EXTRA
, condition
->left
) != sm
)
276 switch (condition
->op
) {
277 case SPECIAL_NOTEQUAL
:
279 if (!sval_is_min(end
) && !sval_is_max(end
))
287 if (sval_cmp(end
, start
) > 0)
289 estate
= alloc_estate_range(end
, start
);
290 estate_set_hard_max(estate
);
291 set_extra_expr_mod(iter_var
, estate
);
292 return get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
295 static struct sm_state
*handle_canonical_for_loops(struct statement
*loop
)
297 struct expression
*iter_expr
;
298 struct expression
*condition
;
300 if (!loop
->iterator_post_statement
)
302 if (loop
->iterator_post_statement
->type
!= STMT_EXPRESSION
)
304 iter_expr
= loop
->iterator_post_statement
->expression
;
305 if (!loop
->iterator_pre_condition
)
307 if (loop
->iterator_pre_condition
->type
!= EXPR_COMPARE
)
309 condition
= loop
->iterator_pre_condition
;
311 if (iter_expr
->op
== SPECIAL_INCREMENT
)
312 return handle_canonical_for_inc(iter_expr
, condition
);
313 if (iter_expr
->op
== SPECIAL_DECREMENT
)
314 return handle_canonical_for_dec(iter_expr
, condition
);
318 struct sm_state
*__extra_handle_canonical_loops(struct statement
*loop
, struct state_list
**slist
)
320 struct sm_state
*ret
;
322 __push_fake_cur_slist();
323 if (!loop
->iterator_post_statement
)
324 ret
= handle_canonical_while_count_down(loop
);
326 ret
= handle_canonical_for_loops(loop
);
327 *slist
= __pop_fake_cur_slist();
331 int __iterator_unchanged(struct sm_state
*sm
)
335 if (get_sm_state(my_id
, sm
->name
, sm
->sym
) == sm
)
340 static void while_count_down_after(struct sm_state
*sm
, struct expression
*condition
)
344 /* paranoid checking. prolly not needed */
345 condition
= strip_expr(condition
);
348 if (condition
->type
!= EXPR_PREOP
&& condition
->type
!= EXPR_POSTOP
)
350 if (condition
->op
!= SPECIAL_DECREMENT
)
352 after_value
= estate_min(sm
->state
);
354 set_extra_mod(sm
->name
, sm
->sym
, alloc_estate_sval(after_value
));
357 void __extra_pre_loop_hook_after(struct sm_state
*sm
,
358 struct statement
*iterator
,
359 struct expression
*condition
)
361 struct expression
*iter_expr
;
363 struct smatch_state
*state
;
366 while_count_down_after(sm
, condition
);
370 iter_expr
= iterator
->expression
;
372 if (condition
->type
!= EXPR_COMPARE
)
374 if (iter_expr
->op
== SPECIAL_INCREMENT
) {
375 limit
= sval_binop(estate_max(sm
->state
), '+',
376 sval_type_val(estate_type(sm
->state
), 1));
378 limit
= sval_binop(estate_min(sm
->state
), '-',
379 sval_type_val(estate_type(sm
->state
), 1));
381 if (!estate_has_hard_max(sm
->state
) && !__has_breaks()) {
382 if (iter_expr
->op
== SPECIAL_INCREMENT
)
383 state
= alloc_estate_range(estate_min(sm
->state
), limit
);
385 state
= alloc_estate_range(limit
, estate_max(sm
->state
));
387 state
= alloc_estate_sval(limit
);
389 if (!estate_has_hard_max(sm
->state
))
390 estate_clear_hard_max(state
);
391 set_extra_mod(sm
->name
, sm
->sym
, state
);
394 static struct state_list
*unmatched_slist
;
395 static struct smatch_state
*unmatched_state(struct sm_state
*sm
)
397 struct smatch_state
*state
;
399 if (unmatched_slist
) {
400 state
= get_state_slist(unmatched_slist
, SMATCH_EXTRA
, sm
->name
, sm
->sym
);
404 return alloc_estate_whole(estate_type(sm
->state
));
407 static void clear_the_pointed_at(struct expression
*expr
, struct state_list
*slist
)
411 struct sm_state
*tmp
;
413 name
= expr_to_var_sym(expr
, &sym
);
417 FOR_EACH_PTR(slist
, tmp
) {
418 if (tmp
->name
[0] != '*')
422 if (strcmp(tmp
->name
+ 1, name
) != 0)
424 set_extra_mod(tmp
->name
, tmp
->sym
, alloc_estate_whole(estate_type(tmp
->state
)));
425 } END_FOR_EACH_PTR(tmp
);
431 static void match_function_call(struct expression
*expr
)
433 struct expression
*arg
;
434 struct expression
*tmp
;
435 struct state_list
*slist
;
437 /* if we have the db this is handled in smatch_function_hooks.c */
440 if (inlinable(expr
->fn
))
443 slist
= get_all_states(SMATCH_EXTRA
);
445 FOR_EACH_PTR(expr
->args
, arg
) {
446 tmp
= strip_expr(arg
);
447 if (tmp
->type
== EXPR_PREOP
&& tmp
->op
== '&')
448 set_extra_expr_mod(tmp
->unop
, alloc_estate_whole(get_type(tmp
->unop
)));
450 clear_the_pointed_at(tmp
, slist
);
451 } END_FOR_EACH_PTR(arg
);
456 static int types_equiv_or_pointer(struct symbol
*one
, struct symbol
*two
)
460 if (one
->type
== SYM_PTR
&& two
->type
== SYM_PTR
)
462 return types_equiv(one
, two
);
465 static void match_vanilla_assign(struct expression
*left
, struct expression
*right
)
467 struct range_list
*rl
= NULL
;
468 struct symbol
*right_sym
;
469 struct symbol
*left_type
;
470 struct symbol
*right_type
;
471 char *right_name
= NULL
;
475 struct smatch_state
*state
;
477 name
= expr_to_var_sym(left
, &sym
);
481 left_type
= get_type(left
);
482 right_type
= get_type(right
);
484 right_name
= expr_to_var_sym(right
, &right_sym
);
485 if (right_name
&& right_sym
&&
486 types_equiv_or_pointer(left_type
, right_type
)) {
487 set_equiv(left
, right
);
491 if (get_implied_rl(right
, &rl
)) {
492 rl
= cast_rl(left_type
, rl
);
493 state
= alloc_estate_rl(rl
);
494 if (get_hard_max(right
, &tmp
))
495 estate_set_hard_max(state
);
497 rl
= alloc_whole_rl(right_type
);
498 rl
= cast_rl(left_type
, rl
);
499 state
= alloc_estate_rl(rl
);
501 set_extra_mod(name
, sym
, state
);
503 free_string(right_name
);
506 static int op_remove_assign(int op
)
509 case SPECIAL_ADD_ASSIGN
:
511 case SPECIAL_SUB_ASSIGN
:
513 case SPECIAL_MUL_ASSIGN
:
515 case SPECIAL_DIV_ASSIGN
:
517 case SPECIAL_MOD_ASSIGN
:
519 case SPECIAL_AND_ASSIGN
:
521 case SPECIAL_OR_ASSIGN
:
523 case SPECIAL_XOR_ASSIGN
:
525 case SPECIAL_SHL_ASSIGN
:
526 return SPECIAL_LEFTSHIFT
;
527 case SPECIAL_SHR_ASSIGN
:
528 return SPECIAL_RIGHTSHIFT
;
534 static void match_assign(struct expression
*expr
)
536 struct range_list
*rl
= NULL
;
537 struct expression
*left
;
538 struct expression
*right
;
539 struct expression
*binop_expr
;
540 struct symbol
*left_type
;
541 struct symbol
*right_type
;
544 sval_t left_min
, left_max
;
545 sval_t right_min
, right_max
;
546 sval_t res_min
, res_max
;
548 left
= strip_expr(expr
->left
);
550 right
= strip_expr(expr
->right
);
551 while (right
->type
== EXPR_ASSIGNMENT
&& right
->op
== '=')
552 right
= strip_expr(right
->left
);
554 if (is_condition(expr
->right
))
555 return; /* handled in smatch_condition.c */
556 if (expr
->op
== '=' && right
->type
== EXPR_CALL
)
557 return; /* handled in smatch_function_hooks.c */
558 if (expr
->op
== '=') {
559 match_vanilla_assign(left
, right
);
563 name
= expr_to_var_sym(left
, &sym
);
567 left_type
= get_type(left
);
568 right_type
= get_type(right
);
570 res_min
= sval_type_min(right_type
);
571 res_max
= sval_type_max(right_type
);
574 case SPECIAL_ADD_ASSIGN
:
575 get_absolute_max(left
, &left_max
);
576 get_absolute_max(right
, &right_max
);
577 if (sval_binop_overflows(left_max
, '+', right_max
))
579 if (get_implied_min(left
, &left_min
) &&
580 !sval_is_negative_min(left_min
) &&
581 get_implied_min(right
, &right_min
) &&
582 !sval_is_negative_min(right_min
)) {
583 res_min
= sval_binop(left_min
, '+', right_min
);
584 res_min
= sval_cast(right_type
, res_min
);
586 if (inside_loop()) /* we are assuming loops don't lead to wrapping */
588 res_max
= sval_binop(left_max
, '+', right_max
);
589 res_max
= sval_cast(right_type
, res_max
);
591 case SPECIAL_SUB_ASSIGN
:
592 if (get_implied_max(left
, &left_max
) &&
593 !sval_is_max(left_max
) &&
594 get_implied_min(right
, &right_min
) &&
595 !sval_is_min(right_min
)) {
596 res_max
= sval_binop(left_max
, '-', right_min
);
597 res_max
= sval_cast(right_type
, res_max
);
601 if (get_implied_min(left
, &left_min
) &&
602 !sval_is_min(left_min
) &&
603 get_implied_max(right
, &right_max
) &&
604 !sval_is_max(right_max
)) {
605 res_min
= sval_binop(left_min
, '-', right_max
);
606 res_min
= sval_cast(right_type
, res_min
);
609 case SPECIAL_AND_ASSIGN
:
610 case SPECIAL_MOD_ASSIGN
:
611 binop_expr
= binop_expression(expr
->left
,
612 op_remove_assign(expr
->op
),
614 if (get_implied_rl(binop_expr
, &rl
)) {
615 rl
= cast_rl(left_type
, rl
);
616 set_extra_mod(name
, sym
, alloc_estate_rl(rl
));
620 rl
= cast_rl(left_type
, alloc_rl(res_min
, res_max
));
621 set_extra_mod(name
, sym
, alloc_estate_rl(rl
));
626 static struct smatch_state
*increment_state(struct smatch_state
*state
)
628 sval_t min
= estate_min(state
);
629 sval_t max
= estate_max(state
);
631 if (!estate_rl(state
))
635 max
= sval_type_max(max
.type
);
637 if (!sval_is_min(min
) && !sval_is_max(min
))
639 if (!sval_is_min(max
) && !sval_is_max(max
))
641 return alloc_estate_range(min
, max
);
644 static struct smatch_state
*decrement_state(struct smatch_state
*state
)
646 sval_t min
= estate_min(state
);
647 sval_t max
= estate_max(state
);
649 if (!estate_rl(state
))
653 min
= sval_type_min(min
.type
);
655 if (!sval_is_min(min
) && !sval_is_max(min
))
657 if (!sval_is_min(max
) && !sval_is_max(max
))
659 return alloc_estate_range(min
, max
);
662 static void unop_expr(struct expression
*expr
)
664 struct smatch_state
*state
;
666 if (expr
->smatch_flags
& Handled
)
670 case SPECIAL_INCREMENT
:
671 state
= get_state_expr(SMATCH_EXTRA
, expr
->unop
);
672 state
= increment_state(state
);
674 state
= alloc_estate_whole(get_type(expr
));
675 set_extra_expr_mod(expr
->unop
, state
);
677 case SPECIAL_DECREMENT
:
678 state
= get_state_expr(SMATCH_EXTRA
, expr
->unop
);
679 state
= decrement_state(state
);
681 state
= alloc_estate_whole(get_type(expr
));
682 set_extra_expr_mod(expr
->unop
, state
);
689 static void asm_expr(struct statement
*stmt
)
692 struct expression
*expr
;
696 FOR_EACH_PTR(stmt
->asm_outputs
, expr
) {
698 case 0: /* identifier */
699 case 1: /* constraint */
702 case 2: /* expression */
704 type
= get_type(strip_expr(expr
));
705 set_extra_expr_mod(expr
, alloc_estate_whole(type
));
708 } END_FOR_EACH_PTR(expr
);
711 static void delete_state_tracker(struct tracker
*t
)
713 remove_from_equiv(t
->name
, t
->sym
);
714 delete_state(t
->owner
, t
->name
, t
->sym
);
717 static void scoped_state_extra(const char *name
, struct symbol
*sym
)
721 t
= alloc_tracker(SMATCH_EXTRA
, name
, sym
);
722 add_scope_hook((scope_hook
*)&delete_state_tracker
, t
);
725 static void match_declarations(struct symbol
*sym
)
730 name
= sym
->ident
->name
;
731 if (!sym
->initializer
) {
732 set_state(SMATCH_EXTRA
, name
, sym
, alloc_estate_whole(get_real_base_type(sym
)));
733 scoped_state_extra(name
, sym
);
738 static void check_dereference(struct expression
*expr
)
740 set_extra_expr_nomod(expr
, alloc_estate_range(valid_ptr_min_sval
, valid_ptr_max_sval
));
743 static void match_dereferences(struct expression
*expr
)
745 if (expr
->type
!= EXPR_PREOP
)
747 check_dereference(expr
->unop
);
750 static void match_pointer_as_array(struct expression
*expr
)
754 check_dereference(expr
->unop
->left
);
757 static void set_param_dereferenced(struct expression
*arg
, char *unused
)
759 check_dereference(arg
);
762 static void match_function_def(struct symbol
*sym
)
766 FOR_EACH_PTR(sym
->ctype
.base_type
->arguments
, arg
) {
769 set_state(my_id
, arg
->ident
->name
, arg
, alloc_estate_whole(get_real_base_type(arg
)));
770 } END_FOR_EACH_PTR(arg
);
773 static sval_t
add_one(sval_t sval
)
779 static sval_t
sub_one(sval_t sval
)
785 static void handle_comparison(struct symbol
*type
, struct expression
*left
, int op
, struct expression
*right
)
787 struct range_list
*left_orig
;
788 struct range_list
*left_true
;
789 struct range_list
*left_false
;
790 struct range_list
*right_orig
;
791 struct range_list
*right_true
;
792 struct range_list
*right_false
;
793 struct smatch_state
*left_true_state
;
794 struct smatch_state
*left_false_state
;
795 struct smatch_state
*right_true_state
;
796 struct smatch_state
*right_false_state
;
797 sval_t min
, max
, dummy
;
799 int right_postop
= 0;
801 if (left
->op
== SPECIAL_INCREMENT
|| left
->op
== SPECIAL_DECREMENT
) {
802 if (left
->type
== EXPR_POSTOP
) {
803 left
->smatch_flags
|= Handled
;
804 left_postop
= left
->op
;
806 left
= strip_expr(left
->unop
);
808 while (left
->type
== EXPR_ASSIGNMENT
)
809 left
= strip_expr(left
->left
);
811 if (right
->op
== SPECIAL_INCREMENT
|| right
->op
== SPECIAL_DECREMENT
) {
812 if (right
->type
== EXPR_POSTOP
) {
813 right
->smatch_flags
|= Handled
;
814 right_postop
= right
->op
;
816 right
= strip_expr(right
->unop
);
819 if (get_implied_rl(left
, &left_orig
)) {
820 left_orig
= cast_rl(type
, left_orig
);
822 min
= sval_type_min(get_type(left
));
823 max
= sval_type_max(get_type(left
));
824 left_orig
= cast_rl(type
, alloc_rl(min
, max
));
827 if (get_implied_rl(right
, &right_orig
)) {
828 right_orig
= cast_rl(type
, right_orig
);
830 min
= sval_type_min(get_type(right
));
831 max
= sval_type_max(get_type(right
));
832 right_orig
= cast_rl(type
, alloc_rl(min
, max
));
834 min
= sval_type_min(type
);
835 max
= sval_type_max(type
);
837 left_true
= clone_rl(left_orig
);
838 left_false
= clone_rl(left_orig
);
839 right_true
= clone_rl(right_orig
);
840 right_false
= clone_rl(right_orig
);
844 case SPECIAL_UNSIGNED_LT
:
845 left_true
= remove_range(left_orig
, rl_max(right_orig
), max
);
846 if (!sval_is_min(rl_min(right_orig
))) {
847 left_false
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
850 right_true
= remove_range(right_orig
, min
, rl_min(left_orig
));
851 if (!sval_is_max(rl_max(left_orig
)))
852 right_false
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
854 case SPECIAL_UNSIGNED_LTE
:
856 if (!sval_is_max(rl_max(right_orig
)))
857 left_true
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
858 left_false
= remove_range(left_orig
, min
, rl_min(right_orig
));
860 if (!sval_is_min(rl_min(left_orig
)))
861 right_true
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
862 right_false
= remove_range(right_orig
, rl_max(left_orig
), max
);
864 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
865 left_false
= remove_range(left_false
, rl_min(left_orig
), rl_min(left_orig
));
866 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
867 right_false
= remove_range(right_false
, rl_max(left_orig
), rl_max(left_orig
));
870 if (!sval_is_max(rl_max(right_orig
))) {
871 left_true
= remove_range(left_true
, add_one(rl_max(right_orig
)), max
);
873 if (!sval_is_min(rl_min(right_orig
))) {
874 left_true
= remove_range(left_true
, min
, sub_one(rl_min(right_orig
)));
876 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
877 left_false
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
879 if (!sval_is_max(rl_max(left_orig
)))
880 right_true
= remove_range(right_true
, add_one(rl_max(left_orig
)), max
);
881 if (!sval_is_min(rl_min(left_orig
)))
882 right_true
= remove_range(right_true
, min
, sub_one(rl_min(left_orig
)));
883 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
884 right_false
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
886 case SPECIAL_UNSIGNED_GTE
:
888 if (!sval_is_min(rl_min(right_orig
)))
889 left_true
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
890 left_false
= remove_range(left_orig
, rl_max(right_orig
), max
);
892 if (!sval_is_max(rl_max(left_orig
)))
893 right_true
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
894 right_false
= remove_range(right_orig
, min
, rl_min(left_orig
));
896 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
897 right_false
= remove_range(right_false
, rl_min(left_orig
), rl_min(left_orig
));
898 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
899 left_false
= remove_range(left_false
, rl_max(left_orig
), rl_max(left_orig
));
902 case SPECIAL_UNSIGNED_GT
:
903 left_true
= remove_range(left_orig
, min
, rl_min(right_orig
));
904 if (!sval_is_max(rl_max(right_orig
)))
905 left_false
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
907 right_true
= remove_range(right_orig
, rl_max(left_orig
), max
);
908 if (!sval_is_min(rl_min(left_orig
)))
909 right_false
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
911 case SPECIAL_NOTEQUAL
:
912 if (!sval_is_max(rl_max(right_orig
)))
913 left_false
= remove_range(left_false
, add_one(rl_max(right_orig
)), max
);
914 if (!sval_is_min(rl_min(right_orig
)))
915 left_false
= remove_range(left_false
, min
, sub_one(rl_min(right_orig
)));
916 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
917 left_true
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
919 if (!sval_is_max(rl_max(left_orig
)))
920 right_false
= remove_range(right_false
, add_one(rl_max(left_orig
)), max
);
921 if (!sval_is_min(rl_min(left_orig
)))
922 right_false
= remove_range(right_false
, min
, sub_one(rl_min(left_orig
)));
923 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
924 right_true
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
930 left_true
= rl_truncate_cast(get_type(left
), left_true
);
931 left_false
= rl_truncate_cast(get_type(left
), left_false
);
932 right_true
= rl_truncate_cast(get_type(right
), right_true
);
933 right_false
= rl_truncate_cast(get_type(right
), right_false
);
935 left_true_state
= alloc_estate_rl(left_true
);
936 left_false_state
= alloc_estate_rl(left_false
);
937 right_true_state
= alloc_estate_rl(right_true
);
938 right_false_state
= alloc_estate_rl(right_false
);
942 case SPECIAL_UNSIGNED_LT
:
943 case SPECIAL_UNSIGNED_LTE
:
945 if (get_hard_max(right
, &dummy
))
946 estate_set_hard_max(left_true_state
);
947 if (get_hard_max(left
, &dummy
))
948 estate_set_hard_max(right_false_state
);
951 case SPECIAL_UNSIGNED_GT
:
952 case SPECIAL_UNSIGNED_GTE
:
954 if (get_hard_max(left
, &dummy
))
955 estate_set_hard_max(right_true_state
);
956 if (get_hard_max(right
, &dummy
))
957 estate_set_hard_max(left_false_state
);
961 if (get_hard_max(left
, &dummy
)) {
962 estate_set_hard_max(left_true_state
);
963 estate_set_hard_max(left_false_state
);
965 if (get_hard_max(right
, &dummy
)) {
966 estate_set_hard_max(right_true_state
);
967 estate_set_hard_max(right_false_state
);
970 if (left_postop
== SPECIAL_INCREMENT
) {
971 left_true_state
= increment_state(left_true_state
);
972 left_false_state
= increment_state(left_false_state
);
974 if (left_postop
== SPECIAL_DECREMENT
) {
975 left_true_state
= decrement_state(left_true_state
);
976 left_false_state
= decrement_state(left_false_state
);
978 if (right_postop
== SPECIAL_INCREMENT
) {
979 right_true_state
= increment_state(right_true_state
);
980 right_false_state
= increment_state(right_false_state
);
982 if (right_postop
== SPECIAL_DECREMENT
) {
983 right_true_state
= decrement_state(right_true_state
);
984 right_false_state
= decrement_state(right_false_state
);
987 set_extra_expr_true_false(left
, left_true_state
, left_false_state
);
988 set_extra_expr_true_false(right
, right_true_state
, right_false_state
);
991 static int opposite_op(int op
)
1002 static int is_simple_math(struct expression
*expr
)
1006 if (expr
->type
!= EXPR_BINOP
)
1008 if (!opposite_op(expr
->op
))
1013 static void move_known_values(struct expression
**left_p
, struct expression
**right_p
)
1015 struct expression
*left
= *left_p
;
1016 struct expression
*right
= *right_p
;
1019 if (get_value(left
, &sval
)) {
1020 if (!is_simple_math(right
))
1022 if (right
->op
== '+' && get_value(right
->left
, &sval
)) {
1023 *left_p
= binop_expression(left
, opposite_op(right
->op
), right
->left
);
1024 *right_p
= right
->right
;
1027 if (get_value(right
->right
, &sval
)) {
1028 *left_p
= binop_expression(left
, opposite_op(right
->op
), right
->right
);
1029 *right_p
= right
->left
;
1034 if (get_value(right
, &sval
)) {
1035 if (!is_simple_math(left
))
1037 if (left
->op
== '+' && get_value(left
->left
, &sval
)) {
1038 *right_p
= binop_expression(right
, opposite_op(left
->op
), left
->left
);
1039 *left_p
= left
->right
;
1043 if (get_value(left
->right
, &sval
)) {
1044 *right_p
= binop_expression(right
, opposite_op(left
->op
), left
->right
);
1045 *left_p
= left
->left
;
1052 static int match_func_comparison(struct expression
*expr
)
1054 struct expression
*left
= strip_expr(expr
->left
);
1055 struct expression
*right
= strip_expr(expr
->right
);
1059 * fixme: think about this harder. We should always be trying to limit
1060 * the non-call side as well. If we can't determine the limitter does
1061 * that mean we aren't querying the database and are missing important
1065 if (left
->type
== EXPR_CALL
) {
1066 if (get_implied_value(left
, &sval
)) {
1067 handle_comparison(get_type(expr
), left
, expr
->op
, right
);
1070 if (!get_implied_value(right
, &sval
))
1072 function_comparison(expr
->op
, left
, sval
, 1);
1076 if (right
->type
== EXPR_CALL
) {
1077 if (get_implied_value(right
, &sval
)) {
1078 handle_comparison(get_type(expr
), left
, expr
->op
, right
);
1081 if (!get_implied_value(left
, &sval
))
1083 function_comparison(expr
->op
, right
, sval
, 0);
1090 static void match_comparison(struct expression
*expr
)
1092 struct expression
*left_orig
= strip_expr(expr
->left
);
1093 struct expression
*right_orig
= strip_expr(expr
->right
);
1094 struct expression
*left
, *right
;
1095 struct expression
*prev
;
1096 struct symbol
*type
;
1098 if (match_func_comparison(expr
))
1101 type
= get_type(expr
);
1103 type
= &llong_ctype
;
1107 move_known_values(&left
, &right
);
1108 handle_comparison(type
, left
, expr
->op
, right
);
1110 prev
= get_assigned_expr(left_orig
);
1111 if (is_simple_math(prev
) && has_variable(prev
, left_orig
) == 0) {
1114 move_known_values(&left
, &right
);
1115 handle_comparison(type
, left
, expr
->op
, right
);
1118 prev
= get_assigned_expr(right_orig
);
1119 if (is_simple_math(prev
) && has_variable(prev
, right_orig
) == 0) {
1122 move_known_values(&left
, &right
);
1123 handle_comparison(type
, left
, expr
->op
, right
);
1127 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
1128 void __extra_match_condition(struct expression
*expr
)
1132 struct smatch_state
*pre_state
;
1133 struct smatch_state
*true_state
;
1134 struct smatch_state
*false_state
;
1136 expr
= strip_expr(expr
);
1137 switch (expr
->type
) {
1139 function_comparison(SPECIAL_NOTEQUAL
, expr
, ll_to_sval(0), 1);
1146 zero
= sval_blank(expr
);
1149 name
= expr_to_var_sym(expr
, &sym
);
1152 pre_state
= get_state(my_id
, name
, sym
);
1153 true_state
= estate_filter_sval(pre_state
, zero
);
1154 if (possibly_true(expr
, SPECIAL_EQUAL
, zero_expr()))
1155 false_state
= alloc_estate_sval(zero
);
1157 false_state
= alloc_estate_empty();
1158 set_extra_true_false(name
, sym
, true_state
, false_state
);
1163 match_comparison(expr
);
1165 case EXPR_ASSIGNMENT
:
1166 __extra_match_condition(expr
->left
);
1171 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
1172 int implied_not_equal(struct expression
*expr
, long long val
)
1174 return !possibly_false(expr
, SPECIAL_NOTEQUAL
, value_expr(val
));
1177 static void struct_member_callback(struct expression
*call
, int param
, char *printed_name
, struct smatch_state
*state
)
1179 if (estate_is_whole(state
))
1181 sql_insert_caller_info(call
, PARAM_VALUE
, param
, printed_name
, state
->name
);
1184 static void db_limited_before(void)
1186 unmatched_slist
= clone_slist(__get_cur_slist());
1189 static void db_limited_after(void)
1191 free_slist(&unmatched_slist
);
1194 static void db_param_limit_filter(struct expression
*expr
, int param
, char *key
, char *value
, int mod
)
1196 struct expression
*arg
;
1199 struct sm_state
*sm
;
1200 struct symbol
*type
;
1201 struct range_list
*rl
;
1202 struct range_list
*limit
;
1203 struct range_list
*new;
1205 while (expr
->type
== EXPR_ASSIGNMENT
)
1206 expr
= strip_expr(expr
->right
);
1207 if (expr
->type
!= EXPR_CALL
)
1210 arg
= get_argument_from_call_expr(expr
->args
, param
);
1214 name
= get_variable_from_key(arg
, key
, &sym
);
1218 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
1219 type
= get_member_type_from_key(arg
, key
);
1221 rl
= estate_rl(sm
->state
);
1223 rl
= alloc_whole_rl(type
);
1225 call_results_to_rl(expr
, type
, value
, &limit
);
1226 new = rl_intersection(rl
, limit
);
1228 /* We want to preserve the implications here */
1229 if (sm
&& rl_equiv(estate_rl(sm
->state
), new)) {
1233 set_extra_mod(name
, sym
, alloc_estate_rl(new));
1235 set_extra_nomod(name
, sym
, alloc_estate_rl(new));
1242 static void db_param_limit(struct expression
*expr
, int param
, char *key
, char *value
)
1244 db_param_limit_filter(expr
, param
, key
, value
, 0);
1247 static void db_param_filter(struct expression
*expr
, int param
, char *key
, char *value
)
1249 db_param_limit_filter(expr
, param
, key
, value
, 1);
1252 static void db_param_add(struct expression
*expr
, int param
, char *key
, char *value
)
1254 struct expression
*arg
;
1257 struct symbol
*type
;
1258 struct smatch_state
*state
;
1259 struct range_list
*added
= NULL
;
1260 struct range_list
*new;
1262 while (expr
->type
== EXPR_ASSIGNMENT
)
1263 expr
= strip_expr(expr
->right
);
1264 if (expr
->type
!= EXPR_CALL
)
1267 arg
= get_argument_from_call_expr(expr
->args
, param
);
1270 name
= get_variable_from_key(arg
, key
, &sym
);
1274 type
= get_member_type_from_key(arg
, key
);
1275 state
= get_state(SMATCH_EXTRA
, name
, sym
);
1277 call_results_to_rl(expr
, type
, value
, &added
);
1278 new = rl_union(estate_rl(state
), added
);
1280 new = alloc_whole_rl(type
);
1283 set_extra_mod(name
, sym
, alloc_estate_rl(new));
1288 static void db_returned_member_info(struct expression
*expr
, int param
, char *key
, char *value
)
1290 struct symbol
*type
;
1293 char member_name
[256];
1294 struct range_list
*rl
;
1296 if (expr
->type
!= EXPR_ASSIGNMENT
)
1299 name
= expr_to_var_sym(expr
->left
, &sym
);
1302 snprintf(member_name
, sizeof(member_name
), "%s%s", name
, key
+ 2);
1303 type
= get_member_type_from_key(expr
->left
, key
);
1306 call_results_to_rl(expr
->right
, type
, value
, &rl
);
1307 set_extra_mod(member_name
, sym
, alloc_estate_rl(rl
));
1313 static void returned_member_callback(int return_id
, char *return_ranges
, char *printed_name
, struct smatch_state
*state
)
1315 if (estate_is_whole(state
))
1318 sql_insert_return_states(return_id
, return_ranges
, RETURN_VALUE
, -1,
1319 printed_name
, state
->name
);
1322 static void match_call_info(struct expression
*expr
)
1324 struct range_list
*rl
= NULL
;
1325 struct expression
*arg
;
1326 struct symbol
*type
;
1329 FOR_EACH_PTR(expr
->args
, arg
) {
1330 type
= get_arg_type(expr
->fn
, i
);
1332 if (get_implied_rl(arg
, &rl
))
1333 rl
= cast_rl(type
, rl
);
1335 rl
= cast_rl(type
, alloc_whole_rl(get_type(arg
)));
1337 sql_insert_caller_info(expr
, PARAM_VALUE
, i
, "$$", show_rl(rl
));
1339 } END_FOR_EACH_PTR(arg
);
1342 static void set_param_value(const char *name
, struct symbol
*sym
, char *key
, char *value
)
1344 struct range_list
*rl
= NULL
;
1345 struct smatch_state
*state
;
1346 struct symbol
*type
;
1349 if (strcmp(key
, "*$$") == 0)
1350 snprintf(fullname
, sizeof(fullname
), "*%s", name
);
1351 else if (strncmp(key
, "$$", 2) == 0)
1352 snprintf(fullname
, 256, "%s%s", name
, key
+ 2);
1356 type
= get_member_type_from_key(symbol_expression(sym
), key
);
1357 str_to_rl(type
, value
, &rl
);
1358 state
= alloc_estate_rl(rl
);
1359 set_state(SMATCH_EXTRA
, fullname
, sym
, state
);
1362 void register_smatch_extra(int id
)
1366 add_merge_hook(my_id
, &merge_estates
);
1367 add_unmatched_state_hook(my_id
, &unmatched_state
);
1368 add_hook(&match_function_def
, FUNC_DEF_HOOK
);
1369 add_hook(&match_declarations
, DECLARATION_HOOK
);
1370 select_caller_info_hook(set_param_value
, PARAM_VALUE
);
1371 select_return_states_hook(RETURN_VALUE
, &db_returned_member_info
);
1372 select_return_states_before(&db_limited_before
);
1373 select_return_states_hook(LIMITED_VALUE
, &db_param_limit
);
1374 select_return_states_hook(FILTER_VALUE
, &db_param_filter
);
1375 select_return_states_hook(ADDED_VALUE
, &db_param_add
);
1376 select_return_states_after(&db_limited_after
);
1379 void register_smatch_extra_late(int id
)
1381 add_hook(&match_dereferences
, DEREF_HOOK
);
1382 add_hook(&match_pointer_as_array
, OP_HOOK
);
1383 select_call_implies_hook(DEREFERENCE
, &set_param_dereferenced
);
1384 add_hook(&match_function_call
, FUNCTION_CALL_HOOK
);
1385 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
1386 add_hook(&unop_expr
, OP_HOOK
);
1387 add_hook(&asm_expr
, ASM_HOOK
);
1389 add_hook(&match_call_info
, FUNCTION_CALL_HOOK
);
1390 add_member_info_callback(my_id
, struct_member_callback
);
1391 add_returned_member_callback(my_id
, returned_member_callback
);