2 * Copyright (C) 2008 Dan Carpenter.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
19 * smatch_extra.c is supposed to track the value of every variable.
31 #include "smatch_slist.h"
32 #include "smatch_extra.h"
36 struct string_list
*__ignored_macros
= NULL
;
37 static int in_warn_on_macro(void)
39 struct statement
*stmt
;
43 stmt
= get_current_statement();
46 macro
= get_macro_name(stmt
->pos
);
50 FOR_EACH_PTR(__ignored_macros
, tmp
) {
51 if (!strcmp(tmp
, macro
))
53 } END_FOR_EACH_PTR(tmp
);
57 typedef void (mod_hook
)(const char *name
, struct symbol
*sym
, struct smatch_state
*state
);
58 DECLARE_PTR_LIST(void_fn_list
, mod_hook
*);
59 static struct void_fn_list
*extra_mod_hooks
;
60 void add_extra_mod_hook(mod_hook
*fn
)
62 mod_hook
**p
= malloc(sizeof(mod_hook
*));
64 add_ptr_list(&extra_mod_hooks
, p
);
67 void call_extra_mod_hooks(const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
71 FOR_EACH_PTR(extra_mod_hooks
, fn
) {
72 (*fn
)(name
, sym
, state
);
73 } END_FOR_EACH_PTR(fn
);
76 struct sm_state
*set_extra_mod_helper(const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
78 remove_from_equiv(name
, sym
);
79 call_extra_mod_hooks(name
, sym
, state
);
80 if (__in_fake_assign
&& estate_is_unknown(state
) && !get_state(SMATCH_EXTRA
, name
, sym
))
82 return set_state(SMATCH_EXTRA
, name
, sym
, state
);
85 static char *get_other_name_sym(const char *name
, struct symbol
*sym
, struct symbol
**new_sym
)
87 struct expression
*assigned
;
88 char *orig_name
= NULL
;
98 skip
= strlen(sym
->ident
->name
);
99 if (name
[skip
] != '-' || name
[skip
+ 1] != '>')
103 assigned
= get_assigned_expr_name_sym(sym
->ident
->name
, sym
);
106 if (assigned
->type
== EXPR_PREOP
|| assigned
->op
== '&') {
108 orig_name
= expr_to_var_sym(assigned
, new_sym
);
109 if (!orig_name
|| !*new_sym
)
112 snprintf(buf
, sizeof(buf
), "%s.%s", orig_name
+ 1, name
+ skip
);
113 ret
= alloc_string(buf
);
114 free_string(orig_name
);
118 if (assigned
->type
!= EXPR_DEREF
)
121 orig_name
= expr_to_var_sym(assigned
, new_sym
);
122 if (!orig_name
|| !*new_sym
)
125 snprintf(buf
, sizeof(buf
), "%s->%s", orig_name
, name
+ skip
);
126 ret
= alloc_string(buf
);
127 free_string(orig_name
);
131 free_string(orig_name
);
135 struct sm_state
*set_extra_mod(const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
138 struct symbol
*new_sym
;
141 if (in_warn_on_macro())
143 sm
= set_extra_mod_helper(name
, sym
, state
);
144 new_name
= get_other_name_sym(name
, sym
, &new_sym
);
145 if (new_name
&& new_sym
)
146 set_extra_mod_helper(new_name
, new_sym
, state
);
147 free_string(new_name
);
151 struct sm_state
*set_extra_expr_mod(struct expression
*expr
, struct smatch_state
*state
)
155 struct sm_state
*ret
= NULL
;
157 expr
= strip_expr(expr
);
158 name
= expr_to_var_sym(expr
, &sym
);
161 ret
= set_extra_mod(name
, sym
, state
);
167 void set_extra_nomod(const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
170 struct symbol
*new_sym
;
171 struct relation
*rel
;
172 struct smatch_state
*orig_state
;
174 orig_state
= get_state(SMATCH_EXTRA
, name
, sym
);
176 new_name
= get_other_name_sym(name
, sym
, &new_sym
);
177 if (new_name
&& new_sym
)
178 set_state(SMATCH_EXTRA
, new_name
, new_sym
, state
);
179 free_string(new_name
);
181 if (!estate_related(orig_state
)) {
182 set_state(SMATCH_EXTRA
, name
, sym
, state
);
186 set_related(state
, estate_related(orig_state
));
187 FOR_EACH_PTR(estate_related(orig_state
), rel
) {
188 if (option_debug_related
)
189 sm_msg("%s updating related %s to %s", name
, rel
->name
, state
->name
);
190 set_state(SMATCH_EXTRA
, rel
->name
, rel
->sym
, state
);
191 } END_FOR_EACH_PTR(rel
);
195 * This is for return_implies_state() hooks which modify a SMATCH_EXTRA state
197 void set_extra_expr_nomod(struct expression
*expr
, struct smatch_state
*state
)
202 name
= expr_to_var_sym(expr
, &sym
);
205 set_extra_nomod(name
, sym
, state
);
211 static void set_extra_true_false(const char *name
, struct symbol
*sym
,
212 struct smatch_state
*true_state
,
213 struct smatch_state
*false_state
)
216 struct symbol
*new_sym
;
217 struct relation
*rel
;
218 struct smatch_state
*orig_state
;
220 if (in_warn_on_macro())
223 new_name
= get_other_name_sym(name
, sym
, &new_sym
);
224 if (new_name
&& new_sym
)
225 set_true_false_states(SMATCH_EXTRA
, new_name
, new_sym
, true_state
, false_state
);
226 free_string(new_name
);
228 orig_state
= get_state(SMATCH_EXTRA
, name
, sym
);
230 if (!estate_related(orig_state
)) {
231 set_true_false_states(SMATCH_EXTRA
, name
, sym
, true_state
, false_state
);
236 set_related(true_state
, estate_related(orig_state
));
238 set_related(false_state
, estate_related(orig_state
));
240 FOR_EACH_PTR(estate_related(orig_state
), rel
) {
241 set_true_false_states(SMATCH_EXTRA
, rel
->name
, rel
->sym
,
242 true_state
, false_state
);
243 } END_FOR_EACH_PTR(rel
);
246 static void set_extra_expr_true_false(struct expression
*expr
,
247 struct smatch_state
*true_state
,
248 struct smatch_state
*false_state
)
253 expr
= strip_expr(expr
);
254 name
= expr_to_var_sym(expr
, &sym
);
257 set_extra_true_false(name
, sym
, true_state
, false_state
);
262 static struct sm_state
*handle_canonical_while_count_down(struct statement
*loop
)
264 struct expression
*iter_var
;
265 struct expression
*condition
;
267 struct smatch_state
*estate
;
270 condition
= strip_expr(loop
->iterator_pre_condition
);
273 if (condition
->type
!= EXPR_PREOP
&& condition
->type
!= EXPR_POSTOP
)
275 if (condition
->op
!= SPECIAL_DECREMENT
)
278 iter_var
= condition
->unop
;
279 sm
= get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
282 if (sval_cmp_val(estate_min(sm
->state
), 0) < 0)
284 start
= estate_max(sm
->state
);
285 if (sval_cmp_val(start
, 0) <= 0)
287 if (!sval_is_max(start
))
290 if (condition
->type
== EXPR_PREOP
) {
291 estate
= alloc_estate_range(sval_type_val(start
.type
, 1), start
);
292 if (estate_has_hard_max(sm
->state
))
293 estate_set_hard_max(estate
);
294 estate_copy_fuzzy_max(estate
, sm
->state
);
295 set_extra_expr_mod(iter_var
, estate
);
297 if (condition
->type
== EXPR_POSTOP
) {
298 estate
= alloc_estate_range(sval_type_val(start
.type
, 0), start
);
299 if (estate_has_hard_max(sm
->state
))
300 estate_set_hard_max(estate
);
301 estate_copy_fuzzy_max(estate
, sm
->state
);
302 set_extra_expr_mod(iter_var
, estate
);
304 return get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
307 static struct sm_state
*handle_canonical_for_inc(struct expression
*iter_expr
,
308 struct expression
*condition
)
310 struct expression
*iter_var
;
312 struct smatch_state
*estate
;
313 sval_t start
, end
, max
;
315 iter_var
= iter_expr
->unop
;
316 sm
= get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
319 if (!estate_get_single_value(sm
->state
, &start
))
321 if (get_implied_max(condition
->right
, &end
))
322 end
= sval_cast(get_type(iter_var
), end
);
324 end
= sval_type_max(get_type(iter_var
));
326 if (get_sm_state_expr(SMATCH_EXTRA
, condition
->left
) != sm
)
329 switch (condition
->op
) {
330 case SPECIAL_UNSIGNED_LT
:
331 case SPECIAL_NOTEQUAL
:
333 if (!sval_is_min(end
))
336 case SPECIAL_UNSIGNED_LTE
:
342 if (sval_cmp(end
, start
) < 0)
344 estate
= alloc_estate_range(start
, end
);
345 if (get_hard_max(condition
->right
, &max
)) {
346 estate_set_hard_max(estate
);
347 if (condition
->op
== '<' ||
348 condition
->op
== SPECIAL_UNSIGNED_LT
||
349 condition
->op
== SPECIAL_NOTEQUAL
)
351 estate_set_fuzzy_max(estate
, max
);
353 set_extra_expr_mod(iter_var
, estate
);
354 return get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
357 static struct sm_state
*handle_canonical_for_dec(struct expression
*iter_expr
,
358 struct expression
*condition
)
360 struct expression
*iter_var
;
362 struct smatch_state
*estate
;
365 iter_var
= iter_expr
->unop
;
366 sm
= get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
369 if (!estate_get_single_value(sm
->state
, &start
))
371 if (!get_implied_min(condition
->right
, &end
))
372 end
= sval_type_min(get_type(iter_var
));
373 if (get_sm_state_expr(SMATCH_EXTRA
, condition
->left
) != sm
)
376 switch (condition
->op
) {
377 case SPECIAL_NOTEQUAL
:
379 if (!sval_is_min(end
) && !sval_is_max(end
))
387 if (sval_cmp(end
, start
) > 0)
389 estate
= alloc_estate_range(end
, start
);
390 estate_set_hard_max(estate
);
391 estate_set_fuzzy_max(estate
, estate_get_fuzzy_max(estate
));
392 set_extra_expr_mod(iter_var
, estate
);
393 return get_sm_state_expr(SMATCH_EXTRA
, iter_var
);
396 static struct sm_state
*handle_canonical_for_loops(struct statement
*loop
)
398 struct expression
*iter_expr
;
399 struct expression
*condition
;
401 if (!loop
->iterator_post_statement
)
403 if (loop
->iterator_post_statement
->type
!= STMT_EXPRESSION
)
405 iter_expr
= loop
->iterator_post_statement
->expression
;
406 if (!loop
->iterator_pre_condition
)
408 if (loop
->iterator_pre_condition
->type
!= EXPR_COMPARE
)
410 condition
= loop
->iterator_pre_condition
;
412 if (iter_expr
->op
== SPECIAL_INCREMENT
)
413 return handle_canonical_for_inc(iter_expr
, condition
);
414 if (iter_expr
->op
== SPECIAL_DECREMENT
)
415 return handle_canonical_for_dec(iter_expr
, condition
);
419 struct sm_state
*__extra_handle_canonical_loops(struct statement
*loop
, struct stree
**stree
)
421 struct sm_state
*ret
;
423 __push_fake_cur_stree();
424 if (!loop
->iterator_post_statement
)
425 ret
= handle_canonical_while_count_down(loop
);
427 ret
= handle_canonical_for_loops(loop
);
428 *stree
= __pop_fake_cur_stree();
432 int __iterator_unchanged(struct sm_state
*sm
)
436 if (get_sm_state(my_id
, sm
->name
, sm
->sym
) == sm
)
441 static void while_count_down_after(struct sm_state
*sm
, struct expression
*condition
)
445 /* paranoid checking. prolly not needed */
446 condition
= strip_expr(condition
);
449 if (condition
->type
!= EXPR_PREOP
&& condition
->type
!= EXPR_POSTOP
)
451 if (condition
->op
!= SPECIAL_DECREMENT
)
453 after_value
= estate_min(sm
->state
);
455 set_extra_mod(sm
->name
, sm
->sym
, alloc_estate_sval(after_value
));
458 void __extra_pre_loop_hook_after(struct sm_state
*sm
,
459 struct statement
*iterator
,
460 struct expression
*condition
)
462 struct expression
*iter_expr
;
464 struct smatch_state
*state
;
467 while_count_down_after(sm
, condition
);
471 iter_expr
= iterator
->expression
;
473 if (condition
->type
!= EXPR_COMPARE
)
475 if (iter_expr
->op
== SPECIAL_INCREMENT
) {
476 limit
= sval_binop(estate_max(sm
->state
), '+',
477 sval_type_val(estate_type(sm
->state
), 1));
479 limit
= sval_binop(estate_min(sm
->state
), '-',
480 sval_type_val(estate_type(sm
->state
), 1));
482 if (!estate_has_hard_max(sm
->state
) && !__has_breaks()) {
483 if (iter_expr
->op
== SPECIAL_INCREMENT
)
484 state
= alloc_estate_range(estate_min(sm
->state
), limit
);
486 state
= alloc_estate_range(limit
, estate_max(sm
->state
));
488 state
= alloc_estate_sval(limit
);
490 if (!estate_has_hard_max(sm
->state
)) {
491 estate_clear_hard_max(state
);
493 if (estate_has_fuzzy_max(sm
->state
)) {
494 sval_t hmax
= estate_get_fuzzy_max(sm
->state
);
495 sval_t max
= estate_max(sm
->state
);
497 if (sval_cmp(hmax
, max
) != 0)
498 estate_clear_fuzzy_max(state
);
499 } else if (!estate_has_fuzzy_max(sm
->state
)) {
500 estate_clear_fuzzy_max(state
);
503 set_extra_mod(sm
->name
, sm
->sym
, state
);
506 static struct stree
*unmatched_stree
;
507 static struct smatch_state
*unmatched_state(struct sm_state
*sm
)
509 struct smatch_state
*state
;
511 if (unmatched_stree
) {
512 state
= get_state_stree(unmatched_stree
, SMATCH_EXTRA
, sm
->name
, sm
->sym
);
516 if (parent_is_gone_var_sym(sm
->name
, sm
->sym
))
517 return alloc_estate_empty();
518 return alloc_estate_whole(estate_type(sm
->state
));
521 static void clear_the_pointed_at(struct expression
*expr
)
526 struct sm_state
*tmp
;
528 name
= expr_to_var_sym(expr
, &sym
);
532 stree
= __get_cur_stree();
533 FOR_EACH_MY_SM(SMATCH_EXTRA
, stree
, tmp
) {
534 if (tmp
->name
[0] != '*')
538 if (strcmp(tmp
->name
+ 1, name
) != 0)
540 set_extra_mod(tmp
->name
, tmp
->sym
, alloc_estate_whole(estate_type(tmp
->state
)));
541 } END_FOR_EACH_SM(tmp
);
547 static void match_function_call(struct expression
*expr
)
549 struct expression
*arg
;
550 struct expression
*tmp
;
552 /* if we have the db this is handled in smatch_function_hooks.c */
555 if (inlinable(expr
->fn
))
558 FOR_EACH_PTR(expr
->args
, arg
) {
559 tmp
= strip_expr(arg
);
560 if (tmp
->type
== EXPR_PREOP
&& tmp
->op
== '&')
561 set_extra_expr_mod(tmp
->unop
, alloc_estate_whole(get_type(tmp
->unop
)));
563 clear_the_pointed_at(tmp
);
564 } END_FOR_EACH_PTR(arg
);
567 static int types_equiv_or_pointer(struct symbol
*one
, struct symbol
*two
)
571 if (one
->type
== SYM_PTR
&& two
->type
== SYM_PTR
)
573 return types_equiv(one
, two
);
576 static bool is_non_null_array(struct expression
*expr
)
584 type
= get_type(expr
);
585 if (!type
|| type
->type
!= SYM_ARRAY
)
587 if (expr
->type
== EXPR_SYMBOL
)
589 if (implied_not_equal(expr
, 0))
592 /* verify that it's not the first member of the struct */
593 if (expr
->type
!= EXPR_DEREF
|| !expr
->member
)
595 name
= expr_to_var_sym(expr
, &sym
);
599 type
= get_real_base_type(sym
);
600 if (!type
|| type
->type
!= SYM_PTR
)
602 type
= get_real_base_type(type
);
603 if (type
->type
!= SYM_STRUCT
)
607 FOR_EACH_PTR(type
->symbol_list
, tmp
) {
611 if (strcmp(expr
->member
->name
, tmp
->ident
->name
) == 0) {
616 } END_FOR_EACH_PTR(tmp
);
621 static void match_vanilla_assign(struct expression
*left
, struct expression
*right
)
623 struct range_list
*rl
= NULL
;
624 struct symbol
*right_sym
;
625 struct symbol
*left_type
;
626 struct symbol
*right_type
;
627 char *right_name
= NULL
;
631 struct smatch_state
*state
;
636 name
= expr_to_var_sym(left
, &sym
);
640 left_type
= get_type(left
);
641 right_type
= get_type(right
);
643 right_name
= expr_to_var_sym(right
, &right_sym
);
645 if (!__in_fake_assign
&&
646 !(right
->type
== EXPR_PREOP
&& right
->op
== '&') &&
647 right_name
&& right_sym
&&
648 types_equiv_or_pointer(left_type
, right_type
) &&
649 !has_symbol(right
, sym
)) {
650 set_equiv(left
, right
);
654 if (is_non_null_array(right
)) {
655 state
= alloc_estate_range(array_min_sval
, array_max_sval
);
656 } else if (get_implied_rl(right
, &rl
)) {
657 rl
= cast_rl(left_type
, rl
);
658 state
= alloc_estate_rl(rl
);
659 if (get_hard_max(right
, &max
)) {
660 estate_set_hard_max(state
);
661 estate_set_fuzzy_max(state
, max
);
664 rl
= alloc_whole_rl(right_type
);
665 rl
= cast_rl(left_type
, rl
);
666 state
= alloc_estate_rl(rl
);
668 set_extra_mod(name
, sym
, state
);
670 free_string(right_name
);
673 static int op_remove_assign(int op
)
676 case SPECIAL_ADD_ASSIGN
:
678 case SPECIAL_SUB_ASSIGN
:
680 case SPECIAL_MUL_ASSIGN
:
682 case SPECIAL_DIV_ASSIGN
:
684 case SPECIAL_MOD_ASSIGN
:
686 case SPECIAL_AND_ASSIGN
:
688 case SPECIAL_OR_ASSIGN
:
690 case SPECIAL_XOR_ASSIGN
:
692 case SPECIAL_SHL_ASSIGN
:
693 return SPECIAL_LEFTSHIFT
;
694 case SPECIAL_SHR_ASSIGN
:
695 return SPECIAL_RIGHTSHIFT
;
701 static void match_assign(struct expression
*expr
)
703 struct range_list
*rl
= NULL
;
704 struct expression
*left
;
705 struct expression
*right
;
706 struct expression
*binop_expr
;
707 struct symbol
*left_type
;
708 struct symbol
*right_type
;
711 sval_t left_min
, left_max
;
712 sval_t right_min
, right_max
;
713 sval_t res_min
, res_max
;
715 left
= strip_expr(expr
->left
);
717 right
= strip_expr(expr
->right
);
718 while (right
->type
== EXPR_ASSIGNMENT
&& right
->op
== '=')
719 right
= strip_expr(right
->left
);
721 if (expr
->op
== '=' && is_condition(expr
->right
))
722 return; /* handled in smatch_condition.c */
723 if (expr
->op
== '=' && right
->type
== EXPR_CALL
)
724 return; /* handled in smatch_function_hooks.c */
725 if (expr
->op
== '=') {
726 match_vanilla_assign(left
, right
);
730 name
= expr_to_var_sym(left
, &sym
);
734 left_type
= get_type(left
);
735 right_type
= get_type(right
);
737 res_min
= sval_type_min(left_type
);
738 res_max
= sval_type_max(left_type
);
741 case SPECIAL_ADD_ASSIGN
:
742 get_absolute_max(left
, &left_max
);
743 get_absolute_max(right
, &right_max
);
744 if (sval_binop_overflows(left_max
, '+', right_max
))
746 if (get_implied_min(left
, &left_min
) &&
747 !sval_is_negative_min(left_min
) &&
748 get_implied_min(right
, &right_min
) &&
749 !sval_is_negative_min(right_min
)) {
750 res_min
= sval_binop(left_min
, '+', right_min
);
751 res_min
= sval_cast(right_type
, res_min
);
753 if (inside_loop()) /* we are assuming loops don't lead to wrapping */
755 res_max
= sval_binop(left_max
, '+', right_max
);
756 res_max
= sval_cast(right_type
, res_max
);
758 case SPECIAL_SUB_ASSIGN
:
759 if (get_implied_max(left
, &left_max
) &&
760 !sval_is_max(left_max
) &&
761 get_implied_min(right
, &right_min
) &&
762 !sval_is_min(right_min
)) {
763 res_max
= sval_binop(left_max
, '-', right_min
);
764 res_max
= sval_cast(right_type
, res_max
);
768 if (get_implied_min(left
, &left_min
) &&
769 !sval_is_min(left_min
) &&
770 get_implied_max(right
, &right_max
) &&
771 !sval_is_max(right_max
)) {
772 res_min
= sval_binop(left_min
, '-', right_max
);
773 res_min
= sval_cast(right_type
, res_min
);
776 case SPECIAL_AND_ASSIGN
:
777 case SPECIAL_MOD_ASSIGN
:
778 case SPECIAL_SHL_ASSIGN
:
779 case SPECIAL_SHR_ASSIGN
:
780 case SPECIAL_OR_ASSIGN
:
781 case SPECIAL_XOR_ASSIGN
:
782 case SPECIAL_MUL_ASSIGN
:
783 case SPECIAL_DIV_ASSIGN
:
784 binop_expr
= binop_expression(expr
->left
,
785 op_remove_assign(expr
->op
),
787 if (get_absolute_rl(binop_expr
, &rl
)) {
788 rl
= cast_rl(left_type
, rl
);
789 set_extra_mod(name
, sym
, alloc_estate_rl(rl
));
794 rl
= cast_rl(left_type
, alloc_rl(res_min
, res_max
));
795 set_extra_mod(name
, sym
, alloc_estate_rl(rl
));
800 static struct smatch_state
*increment_state(struct smatch_state
*state
)
802 sval_t min
= estate_min(state
);
803 sval_t max
= estate_max(state
);
805 if (!estate_rl(state
))
809 max
= sval_type_max(max
.type
);
811 if (!sval_is_min(min
) && !sval_is_max(min
))
813 if (!sval_is_min(max
) && !sval_is_max(max
))
815 return alloc_estate_range(min
, max
);
818 static struct smatch_state
*decrement_state(struct smatch_state
*state
)
820 sval_t min
= estate_min(state
);
821 sval_t max
= estate_max(state
);
823 if (!estate_rl(state
))
827 min
= sval_type_min(min
.type
);
829 if (!sval_is_min(min
) && !sval_is_max(min
))
831 if (!sval_is_min(max
) && !sval_is_max(max
))
833 return alloc_estate_range(min
, max
);
836 static void unop_expr(struct expression
*expr
)
838 struct smatch_state
*state
;
840 if (expr
->smatch_flags
& Handled
)
844 case SPECIAL_INCREMENT
:
845 state
= get_state_expr(SMATCH_EXTRA
, expr
->unop
);
846 state
= increment_state(state
);
848 state
= alloc_estate_whole(get_type(expr
));
849 set_extra_expr_mod(expr
->unop
, state
);
851 case SPECIAL_DECREMENT
:
852 state
= get_state_expr(SMATCH_EXTRA
, expr
->unop
);
853 state
= decrement_state(state
);
855 state
= alloc_estate_whole(get_type(expr
));
856 set_extra_expr_mod(expr
->unop
, state
);
863 static void asm_expr(struct statement
*stmt
)
866 struct expression
*expr
;
870 FOR_EACH_PTR(stmt
->asm_outputs
, expr
) {
872 case 0: /* identifier */
873 case 1: /* constraint */
876 case 2: /* expression */
878 type
= get_type(strip_expr(expr
));
879 set_extra_expr_mod(expr
, alloc_estate_whole(type
));
882 } END_FOR_EACH_PTR(expr
);
885 static void delete_state_tracker(struct tracker
*t
)
887 remove_from_equiv(t
->name
, t
->sym
);
888 delete_state(t
->owner
, t
->name
, t
->sym
);
891 static void scoped_state_extra(const char *name
, struct symbol
*sym
)
895 t
= alloc_tracker(SMATCH_EXTRA
, name
, sym
);
896 add_scope_hook((scope_hook
*)&delete_state_tracker
, t
);
899 static void match_declarations(struct symbol
*sym
)
904 name
= sym
->ident
->name
;
905 if (!sym
->initializer
) {
906 set_state(SMATCH_EXTRA
, name
, sym
, alloc_estate_whole(get_real_base_type(sym
)));
907 scoped_state_extra(name
, sym
);
912 static void check_dereference(struct expression
*expr
)
914 if (outside_of_function())
916 set_extra_expr_nomod(expr
, alloc_estate_range(valid_ptr_min_sval
, valid_ptr_max_sval
));
919 static void match_dereferences(struct expression
*expr
)
921 if (expr
->type
!= EXPR_PREOP
)
923 check_dereference(expr
->unop
);
926 static void match_pointer_as_array(struct expression
*expr
)
930 check_dereference(get_array_base(expr
));
933 static void set_param_dereferenced(struct expression
*arg
, char *key
, char *unused
)
938 name
= get_variable_from_key(arg
, key
, &sym
);
942 set_extra_nomod(name
, sym
, alloc_estate_range(valid_ptr_min_sval
, valid_ptr_max_sval
));
948 static void match_function_def(struct symbol
*sym
)
952 FOR_EACH_PTR(sym
->ctype
.base_type
->arguments
, arg
) {
955 set_state(my_id
, arg
->ident
->name
, arg
, alloc_estate_whole(get_real_base_type(arg
)));
956 } END_FOR_EACH_PTR(arg
);
959 static sval_t
add_one(sval_t sval
)
965 static sval_t
sub_one(sval_t sval
)
971 static void handle_comparison(struct symbol
*type
, struct expression
*left
, int op
, struct expression
*right
)
973 struct range_list
*left_orig
;
974 struct range_list
*left_true
;
975 struct range_list
*left_false
;
976 struct range_list
*right_orig
;
977 struct range_list
*right_true
;
978 struct range_list
*right_false
;
979 struct smatch_state
*left_true_state
;
980 struct smatch_state
*left_false_state
;
981 struct smatch_state
*right_true_state
;
982 struct smatch_state
*right_false_state
;
983 sval_t min
, max
, dummy
, hard_max
;
985 int right_postop
= 0;
987 if (left
->op
== SPECIAL_INCREMENT
|| left
->op
== SPECIAL_DECREMENT
) {
988 if (left
->type
== EXPR_POSTOP
) {
989 left
->smatch_flags
|= Handled
;
990 left_postop
= left
->op
;
992 left
= strip_expr(left
->unop
);
994 while (left
->type
== EXPR_ASSIGNMENT
)
995 left
= strip_expr(left
->left
);
997 if (right
->op
== SPECIAL_INCREMENT
|| right
->op
== SPECIAL_DECREMENT
) {
998 if (right
->type
== EXPR_POSTOP
) {
999 right
->smatch_flags
|= Handled
;
1000 right_postop
= right
->op
;
1002 right
= strip_expr(right
->unop
);
1005 if (get_implied_rl(left
, &left_orig
)) {
1006 left_orig
= cast_rl(type
, left_orig
);
1008 min
= sval_type_min(get_type(left
));
1009 max
= sval_type_max(get_type(left
));
1010 left_orig
= cast_rl(type
, alloc_rl(min
, max
));
1013 if (get_implied_rl(right
, &right_orig
)) {
1014 right_orig
= cast_rl(type
, right_orig
);
1016 min
= sval_type_min(get_type(right
));
1017 max
= sval_type_max(get_type(right
));
1018 right_orig
= cast_rl(type
, alloc_rl(min
, max
));
1020 min
= sval_type_min(type
);
1021 max
= sval_type_max(type
);
1023 left_true
= clone_rl(left_orig
);
1024 left_false
= clone_rl(left_orig
);
1025 right_true
= clone_rl(right_orig
);
1026 right_false
= clone_rl(right_orig
);
1030 case SPECIAL_UNSIGNED_LT
:
1031 left_true
= remove_range(left_orig
, rl_max(right_orig
), max
);
1032 if (!sval_is_min(rl_min(right_orig
))) {
1033 left_false
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
1036 right_true
= remove_range(right_orig
, min
, rl_min(left_orig
));
1037 if (!sval_is_max(rl_max(left_orig
)))
1038 right_false
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
1040 case SPECIAL_UNSIGNED_LTE
:
1042 if (!sval_is_max(rl_max(right_orig
)))
1043 left_true
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
1044 left_false
= remove_range(left_orig
, min
, rl_min(right_orig
));
1046 if (!sval_is_min(rl_min(left_orig
)))
1047 right_true
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
1048 right_false
= remove_range(right_orig
, rl_max(left_orig
), max
);
1050 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
1051 left_false
= remove_range(left_false
, rl_min(left_orig
), rl_min(left_orig
));
1052 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
1053 right_false
= remove_range(right_false
, rl_max(left_orig
), rl_max(left_orig
));
1056 if (!sval_is_max(rl_max(right_orig
))) {
1057 left_true
= remove_range(left_true
, add_one(rl_max(right_orig
)), max
);
1059 if (!sval_is_min(rl_min(right_orig
))) {
1060 left_true
= remove_range(left_true
, min
, sub_one(rl_min(right_orig
)));
1062 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
1063 left_false
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
1065 if (!sval_is_max(rl_max(left_orig
)))
1066 right_true
= remove_range(right_true
, add_one(rl_max(left_orig
)), max
);
1067 if (!sval_is_min(rl_min(left_orig
)))
1068 right_true
= remove_range(right_true
, min
, sub_one(rl_min(left_orig
)));
1069 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
1070 right_false
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
1072 case SPECIAL_UNSIGNED_GTE
:
1074 if (!sval_is_min(rl_min(right_orig
)))
1075 left_true
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
1076 left_false
= remove_range(left_orig
, rl_max(right_orig
), max
);
1078 if (!sval_is_max(rl_max(left_orig
)))
1079 right_true
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
1080 right_false
= remove_range(right_orig
, min
, rl_min(left_orig
));
1082 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
1083 right_false
= remove_range(right_false
, rl_min(left_orig
), rl_min(left_orig
));
1084 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
1085 left_false
= remove_range(left_false
, rl_max(left_orig
), rl_max(left_orig
));
1088 case SPECIAL_UNSIGNED_GT
:
1089 left_true
= remove_range(left_orig
, min
, rl_min(right_orig
));
1090 if (!sval_is_max(rl_max(right_orig
)))
1091 left_false
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
1093 right_true
= remove_range(right_orig
, rl_max(left_orig
), max
);
1094 if (!sval_is_min(rl_min(left_orig
)))
1095 right_false
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
1097 case SPECIAL_NOTEQUAL
:
1098 if (!sval_is_max(rl_max(right_orig
)))
1099 left_false
= remove_range(left_false
, add_one(rl_max(right_orig
)), max
);
1100 if (!sval_is_min(rl_min(right_orig
)))
1101 left_false
= remove_range(left_false
, min
, sub_one(rl_min(right_orig
)));
1102 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
1103 left_true
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
1105 if (!sval_is_max(rl_max(left_orig
)))
1106 right_false
= remove_range(right_false
, add_one(rl_max(left_orig
)), max
);
1107 if (!sval_is_min(rl_min(left_orig
)))
1108 right_false
= remove_range(right_false
, min
, sub_one(rl_min(left_orig
)));
1109 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
1110 right_true
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
1116 left_true
= rl_truncate_cast(get_type(left
), left_true
);
1117 left_false
= rl_truncate_cast(get_type(left
), left_false
);
1118 right_true
= rl_truncate_cast(get_type(right
), right_true
);
1119 right_false
= rl_truncate_cast(get_type(right
), right_false
);
1121 left_true_state
= alloc_estate_rl(left_true
);
1122 left_false_state
= alloc_estate_rl(left_false
);
1123 right_true_state
= alloc_estate_rl(right_true
);
1124 right_false_state
= alloc_estate_rl(right_false
);
1128 case SPECIAL_UNSIGNED_LT
:
1129 case SPECIAL_UNSIGNED_LTE
:
1131 if (get_hard_max(right
, &dummy
))
1132 estate_set_hard_max(left_true_state
);
1133 if (get_hard_max(left
, &dummy
))
1134 estate_set_hard_max(right_false_state
);
1137 case SPECIAL_UNSIGNED_GT
:
1138 case SPECIAL_UNSIGNED_GTE
:
1140 if (get_hard_max(left
, &dummy
))
1141 estate_set_hard_max(right_true_state
);
1142 if (get_hard_max(right
, &dummy
))
1143 estate_set_hard_max(left_false_state
);
1149 case SPECIAL_UNSIGNED_LT
:
1150 case SPECIAL_UNSIGNED_LTE
:
1152 if (get_hard_max(right
, &hard_max
)) {
1153 if (op
== '<' || op
== SPECIAL_UNSIGNED_LT
)
1155 estate_set_fuzzy_max(left_true_state
, hard_max
);
1157 if (get_implied_value(right
, &hard_max
)) {
1158 if (op
== SPECIAL_UNSIGNED_LTE
||
1161 estate_set_fuzzy_max(left_false_state
, hard_max
);
1163 if (get_hard_max(left
, &hard_max
)) {
1164 if (op
== SPECIAL_UNSIGNED_LTE
||
1167 estate_set_fuzzy_max(right_false_state
, hard_max
);
1169 if (get_implied_value(left
, &hard_max
)) {
1170 if (op
== '<' || op
== SPECIAL_UNSIGNED_LT
)
1172 estate_set_fuzzy_max(right_true_state
, hard_max
);
1176 case SPECIAL_UNSIGNED_GT
:
1177 case SPECIAL_UNSIGNED_GTE
:
1179 if (get_hard_max(left
, &hard_max
)) {
1180 if (op
== '>' || op
== SPECIAL_UNSIGNED_GT
)
1182 estate_set_fuzzy_max(right_true_state
, hard_max
);
1184 if (get_implied_value(left
, &hard_max
)) {
1185 if (op
== SPECIAL_UNSIGNED_GTE
||
1188 estate_set_fuzzy_max(right_false_state
, hard_max
);
1190 if (get_hard_max(right
, &hard_max
)) {
1191 if (op
== SPECIAL_UNSIGNED_LTE
||
1194 estate_set_fuzzy_max(left_false_state
, hard_max
);
1196 if (get_implied_value(right
, &hard_max
)) {
1198 op
== SPECIAL_UNSIGNED_GT
)
1200 estate_set_fuzzy_max(left_true_state
, hard_max
);
1204 if (get_hard_max(left
, &hard_max
))
1205 estate_set_fuzzy_max(right_true_state
, hard_max
);
1206 if (get_hard_max(right
, &hard_max
))
1207 estate_set_fuzzy_max(left_true_state
, hard_max
);
1211 if (get_hard_max(left
, &hard_max
)) {
1212 estate_set_hard_max(left_true_state
);
1213 estate_set_hard_max(left_false_state
);
1215 if (get_hard_max(right
, &hard_max
)) {
1216 estate_set_hard_max(right_true_state
);
1217 estate_set_hard_max(right_false_state
);
1220 if (left_postop
== SPECIAL_INCREMENT
) {
1221 left_true_state
= increment_state(left_true_state
);
1222 left_false_state
= increment_state(left_false_state
);
1224 if (left_postop
== SPECIAL_DECREMENT
) {
1225 left_true_state
= decrement_state(left_true_state
);
1226 left_false_state
= decrement_state(left_false_state
);
1228 if (right_postop
== SPECIAL_INCREMENT
) {
1229 right_true_state
= increment_state(right_true_state
);
1230 right_false_state
= increment_state(right_false_state
);
1232 if (right_postop
== SPECIAL_DECREMENT
) {
1233 right_true_state
= decrement_state(right_true_state
);
1234 right_false_state
= decrement_state(right_false_state
);
1237 set_extra_expr_true_false(left
, left_true_state
, left_false_state
);
1238 set_extra_expr_true_false(right
, right_true_state
, right_false_state
);
1241 static int is_simple_math(struct expression
*expr
)
1245 if (expr
->type
!= EXPR_BINOP
)
1256 static void move_known_values(struct expression
**left_p
, struct expression
**right_p
)
1258 struct expression
*left
= *left_p
;
1259 struct expression
*right
= *right_p
;
1262 if (get_implied_value(left
, &sval
)) {
1263 if (!is_simple_math(right
))
1265 if (right
->op
== '*') {
1268 if (!get_value(right
->right
, &divisor
))
1270 if (divisor
.value
== 0 && sval
.value
% divisor
.value
)
1272 *left_p
= binop_expression(left
, invert_op(right
->op
), right
->right
);
1273 *right_p
= right
->left
;
1276 if (right
->op
== '+' && get_value(right
->left
, &sval
)) {
1277 *left_p
= binop_expression(left
, invert_op(right
->op
), right
->left
);
1278 *right_p
= right
->right
;
1281 if (get_value(right
->right
, &sval
)) {
1282 *left_p
= binop_expression(left
, invert_op(right
->op
), right
->right
);
1283 *right_p
= right
->left
;
1288 if (get_implied_value(right
, &sval
)) {
1289 if (!is_simple_math(left
))
1291 if (left
->op
== '*') {
1294 if (!get_value(left
->right
, &divisor
))
1296 if (divisor
.value
== 0 && sval
.value
% divisor
.value
)
1298 *right_p
= binop_expression(right
, invert_op(left
->op
), left
->right
);
1299 *left_p
= left
->left
;
1302 if (left
->op
== '+' && get_value(left
->left
, &sval
)) {
1303 *right_p
= binop_expression(right
, invert_op(left
->op
), left
->left
);
1304 *left_p
= left
->right
;
1308 if (get_value(left
->right
, &sval
)) {
1309 *right_p
= binop_expression(right
, invert_op(left
->op
), left
->right
);
1310 *left_p
= left
->left
;
1317 static int match_func_comparison(struct expression
*expr
)
1319 struct expression
*left
= strip_expr(expr
->left
);
1320 struct expression
*right
= strip_expr(expr
->right
);
1324 * fixme: think about this harder. We should always be trying to limit
1325 * the non-call side as well. If we can't determine the limitter does
1326 * that mean we aren't querying the database and are missing important
1330 if (left
->type
== EXPR_CALL
) {
1331 if (get_implied_value(left
, &sval
)) {
1332 handle_comparison(get_type(expr
), left
, expr
->op
, right
);
1335 function_comparison(left
, expr
->op
, right
);
1339 if (right
->type
== EXPR_CALL
) {
1340 if (get_implied_value(right
, &sval
)) {
1341 handle_comparison(get_type(expr
), left
, expr
->op
, right
);
1344 function_comparison(left
, expr
->op
, right
);
1351 static void match_comparison(struct expression
*expr
)
1353 struct expression
*left_orig
= strip_expr(expr
->left
);
1354 struct expression
*right_orig
= strip_expr(expr
->right
);
1355 struct expression
*left
, *right
;
1356 struct expression
*prev
;
1357 struct symbol
*type
;
1359 if (match_func_comparison(expr
))
1362 type
= get_type(expr
);
1364 type
= &llong_ctype
;
1368 move_known_values(&left
, &right
);
1369 handle_comparison(type
, left
, expr
->op
, right
);
1371 prev
= get_assigned_expr(left_orig
);
1372 if (is_simple_math(prev
) && has_variable(prev
, left_orig
) == 0) {
1375 move_known_values(&left
, &right
);
1376 handle_comparison(type
, left
, expr
->op
, right
);
1379 prev
= get_assigned_expr(right_orig
);
1380 if (is_simple_math(prev
) && has_variable(prev
, right_orig
) == 0) {
1383 move_known_values(&left
, &right
);
1384 handle_comparison(type
, left
, expr
->op
, right
);
1388 static void handle_AND_condition(struct expression
*expr
)
1390 struct range_list
*rl
= NULL
;
1393 if (get_implied_value(expr
->left
, &known
) && known
.value
> 0) {
1395 get_absolute_rl(expr
->right
, &rl
);
1396 rl
= remove_range(rl
, sval_type_val(known
.type
, 0), known
);
1397 set_extra_expr_true_false(expr
->right
, alloc_estate_rl(rl
), NULL
);
1401 if (get_implied_value(expr
->right
, &known
) && known
.value
> 0) {
1403 get_absolute_rl(expr
->left
, &rl
);
1404 rl
= remove_range(rl
, sval_type_val(known
.type
, 0), known
);
1405 set_extra_expr_true_false(expr
->left
, alloc_estate_rl(rl
), NULL
);
1410 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
1411 void __extra_match_condition(struct expression
*expr
)
1415 struct smatch_state
*pre_state
;
1416 struct smatch_state
*true_state
;
1417 struct smatch_state
*false_state
;
1419 expr
= strip_expr(expr
);
1420 switch (expr
->type
) {
1422 function_comparison(expr
, SPECIAL_NOTEQUAL
, zero_expr());
1429 zero
= sval_blank(expr
);
1432 name
= expr_to_var_sym(expr
, &sym
);
1435 pre_state
= get_state(my_id
, name
, sym
);
1436 true_state
= estate_filter_sval(pre_state
, zero
);
1437 if (possibly_true(expr
, SPECIAL_EQUAL
, zero_expr()))
1438 false_state
= alloc_estate_sval(zero
);
1440 false_state
= alloc_estate_empty();
1441 set_extra_true_false(name
, sym
, true_state
, false_state
);
1446 match_comparison(expr
);
1448 case EXPR_ASSIGNMENT
:
1449 __extra_match_condition(expr
->left
);
1452 if (expr
->op
== '&')
1453 handle_AND_condition(expr
);
1458 static void assume_indexes_are_valid(struct expression
*expr
)
1460 struct expression
*array_expr
;
1462 struct expression
*offset
;
1463 struct symbol
*offset_type
;
1464 struct range_list
*rl_before
;
1465 struct range_list
*rl_after
;
1466 struct range_list
*filter
= NULL
;
1469 expr
= strip_expr(expr
);
1470 if (!is_array(expr
))
1473 offset
= get_array_offset(expr
);
1474 offset_type
= get_type(offset
);
1475 if (offset_type
&& type_signed(offset_type
)) {
1476 filter
= alloc_rl(sval_type_min(offset_type
),
1477 sval_type_val(offset_type
, -1));
1480 array_expr
= get_array_base(expr
);
1481 array_size
= get_real_array_size(array_expr
);
1482 if (array_size
> 1) {
1483 size
= sval_type_val(offset_type
, array_size
);
1484 add_range(&filter
, size
, sval_type_max(offset_type
));
1489 get_absolute_rl(offset
, &rl_before
);
1490 rl_after
= rl_filter(rl_before
, filter
);
1491 if (rl_equiv(rl_before
, rl_after
))
1493 set_extra_expr_nomod(offset
, alloc_estate_rl(rl_after
));
1496 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
1497 int implied_not_equal(struct expression
*expr
, long long val
)
1499 return !possibly_false(expr
, SPECIAL_NOTEQUAL
, value_expr(val
));
1502 int implied_not_equal_name_sym(char *name
, struct symbol
*sym
, long long val
)
1504 struct smatch_state
*estate
;
1506 estate
= get_state(SMATCH_EXTRA
, name
, sym
);
1509 if (!rl_has_sval(estate_rl(estate
), sval_type_val(estate_type(estate
), 0)))
1514 int parent_is_null_var_sym(const char *name
, struct symbol
*sym
)
1519 struct smatch_state
*state
;
1521 strncpy(buf
, name
, sizeof(buf
) - 1);
1522 buf
[sizeof(buf
) - 1] = '\0';
1525 while (*start
== '*') {
1527 state
= get_state(SMATCH_EXTRA
, start
, sym
);
1530 if (!estate_rl(state
))
1532 if (estate_min(state
).value
== 0 &&
1533 estate_max(state
).value
== 0)
1538 while (*start
== '&')
1541 while ((end
= strrchr(start
, '-'))) {
1543 state
= get_state(SMATCH_EXTRA
, start
, sym
);
1546 if (estate_min(state
).value
== 0 &&
1547 estate_max(state
).value
== 0)
1553 int parent_is_null(struct expression
*expr
)
1559 expr
= strip_expr(expr
);
1560 var
= expr_to_var_sym(expr
, &sym
);
1563 ret
= parent_is_null_var_sym(var
, sym
);
1569 static int param_used_callback(void *found
, int argc
, char **argv
, char **azColName
)
1575 static int filter_unused_kzalloc_info(struct expression
*call
, int param
, char *printed_name
, struct sm_state
*sm
)
1580 /* for function pointers assume everything is used */
1581 if (call
->fn
->type
!= EXPR_SYMBOL
)
1585 * kzalloc() information is treated as special because so there is just
1586 * a lot of stuff initialized to zero and it makes building the database
1587 * take hours and hours.
1589 * In theory, we should just remove this line and not pass any unused
1590 * information, but I'm not sure enough that this code works so I want
1591 * to hold off on that for now.
1593 if (!estate_get_single_value(sm
->state
, &sval
) || sval
.value
!= 0)
1596 run_sql(¶m_used_callback
, &found
,
1597 "select * from call_implies where %s and type = %d and parameter = %d and key = '%s';",
1598 get_static_filter(call
->fn
->symbol
), PARAM_USED
, param
, printed_name
);
1602 /* If the database is not built yet, then assume everything is used */
1603 run_sql(¶m_used_callback
, &found
,
1604 "select * from call_implies where %s and type = %d;",
1605 get_static_filter(call
->fn
->symbol
), PARAM_USED
);
1612 static void struct_member_callback(struct expression
*call
, int param
, char *printed_name
, struct sm_state
*sm
)
1614 if (estate_is_whole(sm
->state
))
1616 if (filter_unused_kzalloc_info(call
, param
, printed_name
, sm
))
1618 sql_insert_caller_info(call
, PARAM_VALUE
, param
, printed_name
, sm
->state
->name
);
1619 if (estate_has_fuzzy_max(sm
->state
))
1620 sql_insert_caller_info(call
, FUZZY_MAX
, param
, printed_name
,
1621 sval_to_str(estate_get_fuzzy_max(sm
->state
)));
1624 static void db_limited_before(void)
1626 unmatched_stree
= clone_stree(__get_cur_stree());
1629 static void db_limited_after(void)
1631 free_stree(&unmatched_stree
);
1634 static void db_param_limit_filter(struct expression
*expr
, int param
, char *key
, char *value
, enum info_type op
)
1636 struct expression
*arg
;
1639 struct sm_state
*sm
;
1640 struct symbol
*compare_type
, *var_type
;
1641 struct range_list
*rl
;
1642 struct range_list
*limit
;
1643 struct range_list
*new;
1645 while (expr
->type
== EXPR_ASSIGNMENT
)
1646 expr
= strip_expr(expr
->right
);
1647 if (expr
->type
!= EXPR_CALL
)
1650 arg
= get_argument_from_call_expr(expr
->args
, param
);
1654 name
= get_variable_from_key(arg
, key
, &sym
);
1658 if (strcmp(key
, "$") == 0)
1659 compare_type
= get_arg_type(expr
->fn
, param
);
1661 compare_type
= get_member_type_from_key(arg
, key
);
1663 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
1665 rl
= estate_rl(sm
->state
);
1667 rl
= alloc_whole_rl(compare_type
);
1669 call_results_to_rl(expr
, compare_type
, value
, &limit
);
1670 new = rl_intersection(rl
, limit
);
1672 var_type
= get_member_type_from_key(arg
, key
);
1673 new = cast_rl(var_type
, new);
1675 /* We want to preserve the implications here */
1676 if (sm
&& rl_equiv(estate_rl(sm
->state
), new))
1679 if (op
== PARAM_LIMIT
)
1680 set_extra_nomod(name
, sym
, alloc_estate_rl(new));
1682 set_extra_mod(name
, sym
, alloc_estate_rl(new));
1689 static void db_param_limit(struct expression
*expr
, int param
, char *key
, char *value
)
1691 db_param_limit_filter(expr
, param
, key
, value
, PARAM_LIMIT
);
1694 static void db_param_filter(struct expression
*expr
, int param
, char *key
, char *value
)
1696 db_param_limit_filter(expr
, param
, key
, value
, PARAM_FILTER
);
1699 static void db_param_add_set(struct expression
*expr
, int param
, char *key
, char *value
, enum info_type op
)
1701 struct expression
*arg
;
1704 struct symbol
*type
;
1705 struct smatch_state
*state
;
1706 struct range_list
*new = NULL
;
1707 struct range_list
*added
= NULL
;
1709 while (expr
->type
== EXPR_ASSIGNMENT
)
1710 expr
= strip_expr(expr
->right
);
1711 if (expr
->type
!= EXPR_CALL
)
1714 arg
= get_argument_from_call_expr(expr
->args
, param
);
1717 type
= get_member_type_from_key(arg
, key
);
1718 name
= get_variable_from_key(arg
, key
, &sym
);
1722 state
= get_state(SMATCH_EXTRA
, name
, sym
);
1724 new = estate_rl(state
);
1726 call_results_to_rl(expr
, type
, value
, &added
);
1728 if (op
== PARAM_SET
)
1731 new = rl_union(new, added
);
1733 set_extra_mod(name
, sym
, alloc_estate_rl(new));
1738 static void db_param_add(struct expression
*expr
, int param
, char *key
, char *value
)
1740 db_param_add_set(expr
, param
, key
, value
, PARAM_ADD
);
1743 static void db_param_set(struct expression
*expr
, int param
, char *key
, char *value
)
1745 db_param_add_set(expr
, param
, key
, value
, PARAM_SET
);
1748 static void db_returned_member_info(struct expression
*expr
, int param
, char *key
, char *value
)
1750 struct symbol
*type
;
1753 struct range_list
*rl
;
1755 if (expr
->type
!= EXPR_ASSIGNMENT
)
1758 name
= return_state_to_var_sym(expr
, param
, key
, &sym
);
1761 type
= get_member_type_from_key(expr
->left
, key
);
1764 call_results_to_rl(expr
->right
, type
, value
, &rl
);
1765 set_extra_mod(name
, sym
, alloc_estate_rl(rl
));
1771 static char *in_terms_of_param_math(struct expression
*expr
, char *printed_name
)
1778 var
= expr_to_var_sym(expr
, &sym
);
1781 snprintf(buf
, sizeof(buf
), "%s%s", var
, printed_name
+ 2);
1783 ret
= get_value_in_terms_of_parameter_math_var_sym(buf
, sym
);
1790 static void returned_member_callback(int return_id
, char *return_ranges
, struct expression
*expr
, char *printed_name
, struct smatch_state
*state
)
1796 /* these are handled in smatch_param_filter/set/limit.c */
1797 if (printed_name
[0] != '*' &&
1798 !strchr(printed_name
, '.') && !strchr(printed_name
, '-'))
1801 if (estate_get_single_value(state
, &sval
)) {
1802 sql_insert_return_states(return_id
, return_ranges
, RETURN_VALUE
, -1,
1803 printed_name
, sval_to_str(sval
));
1807 math_str
= in_terms_of_param_math(expr
, printed_name
);
1809 snprintf(buf
, sizeof(buf
), "%s[%s]", state
->name
, math_str
);
1810 sql_insert_return_states(return_id
, return_ranges
, RETURN_VALUE
, -1,
1815 if (estate_is_whole(state
))
1818 sql_insert_return_states(return_id
, return_ranges
, RETURN_VALUE
, -1,
1819 printed_name
, state
->name
);
1822 static void match_call_info(struct expression
*expr
)
1824 struct smatch_state
*state
;
1825 struct range_list
*rl
= NULL
;
1826 struct expression
*arg
;
1827 struct symbol
*type
;
1830 FOR_EACH_PTR(expr
->args
, arg
) {
1831 type
= get_arg_type(expr
->fn
, i
);
1833 if (get_implied_rl(arg
, &rl
))
1834 rl
= cast_rl(type
, rl
);
1836 rl
= cast_rl(type
, alloc_whole_rl(get_type(arg
)));
1838 if (!is_whole_rl(rl
))
1839 sql_insert_caller_info(expr
, PARAM_VALUE
, i
, "$", show_rl(rl
));
1840 state
= get_state_expr(SMATCH_EXTRA
, arg
);
1841 if (estate_has_fuzzy_max(state
)) {
1842 sql_insert_caller_info(expr
, FUZZY_MAX
, i
, "$",
1843 sval_to_str(estate_get_fuzzy_max(state
)));
1846 } END_FOR_EACH_PTR(arg
);
1849 static void set_param_value(const char *name
, struct symbol
*sym
, char *key
, char *value
)
1851 struct range_list
*rl
= NULL
;
1852 struct smatch_state
*state
;
1853 struct symbol
*type
;
1856 if (strcmp(key
, "*$") == 0)
1857 snprintf(fullname
, sizeof(fullname
), "*%s", name
);
1858 else if (strncmp(key
, "$", 1) == 0)
1859 snprintf(fullname
, 256, "%s%s", name
, key
+ 1);
1863 type
= get_member_type_from_key(symbol_expression(sym
), key
);
1864 str_to_rl(type
, value
, &rl
);
1865 state
= alloc_estate_rl(rl
);
1866 set_state(SMATCH_EXTRA
, fullname
, sym
, state
);
1869 static void set_param_hard_max(const char *name
, struct symbol
*sym
, char *key
, char *value
)
1871 struct range_list
*rl
= NULL
;
1872 struct smatch_state
*state
;
1873 struct symbol
*type
;
1877 if (strcmp(key
, "*$") == 0)
1878 snprintf(fullname
, sizeof(fullname
), "*%s", name
);
1879 else if (strncmp(key
, "$", 1) == 0)
1880 snprintf(fullname
, 256, "%s%s", name
, key
+ 1);
1884 state
= get_state(SMATCH_EXTRA
, fullname
, sym
);
1887 type
= get_member_type_from_key(symbol_expression(sym
), key
);
1888 str_to_rl(type
, value
, &rl
);
1889 if (!rl_to_sval(rl
, &max
))
1891 estate_set_fuzzy_max(state
, max
);
1894 void register_smatch_extra(int id
)
1898 add_merge_hook(my_id
, &merge_estates
);
1899 add_unmatched_state_hook(my_id
, &unmatched_state
);
1900 add_hook(&match_function_def
, FUNC_DEF_HOOK
);
1901 add_hook(&match_declarations
, DECLARATION_HOOK
);
1902 select_caller_info_hook(set_param_value
, PARAM_VALUE
);
1903 select_caller_info_hook(set_param_hard_max
, FUZZY_MAX
);
1904 select_return_states_hook(RETURN_VALUE
, &db_returned_member_info
);
1905 select_return_states_before(&db_limited_before
);
1906 select_return_states_hook(PARAM_LIMIT
, &db_param_limit
);
1907 select_return_states_hook(PARAM_FILTER
, &db_param_filter
);
1908 select_return_states_hook(PARAM_ADD
, &db_param_add
);
1909 select_return_states_hook(PARAM_SET
, &db_param_set
);
1910 select_return_states_after(&db_limited_after
);
1913 void register_smatch_extra_late(int id
)
1915 add_hook(&match_dereferences
, DEREF_HOOK
);
1916 add_hook(&match_pointer_as_array
, OP_HOOK
);
1917 select_call_implies_hook(DEREFERENCE
, &set_param_dereferenced
);
1918 add_hook(&match_function_call
, FUNCTION_CALL_HOOK
);
1919 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
1920 add_hook(&match_assign
, GLOBAL_ASSIGNMENT_HOOK
);
1921 add_hook(&unop_expr
, OP_HOOK
);
1922 add_hook(&asm_expr
, ASM_HOOK
);
1924 add_hook(&match_call_info
, FUNCTION_CALL_HOOK
);
1925 add_member_info_callback(my_id
, struct_member_callback
);
1926 add_returned_member_callback(my_id
, returned_member_callback
);
1928 add_hook(&assume_indexes_are_valid
, OP_HOOK
);