check_deref_check: get rid of some false positives
[smatch.git] / smatch_extra.c
blob37313e214eec6794a9136565bfdd1de29e69697d
1 /*
2 * sparse/smatch_extra.c
4 * Copyright (C) 2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
11 * smatch_extra.c is supposed to track the value of every variable.
14 #include <stdlib.h>
15 #define __USE_ISOC99
16 #include <limits.h>
17 #include "parse.h"
18 #include "smatch.h"
19 #include "smatch_slist.h"
20 #include "smatch_extra.h"
22 static int my_id;
24 static struct symbol *cur_func;
26 struct data_range whole_range = {
27 .min = LLONG_MIN,
28 .max = LLONG_MAX,
31 static struct smatch_state *alloc_extra_state_empty()
33 struct smatch_state *state;
34 struct data_info *dinfo;
36 dinfo = __alloc_data_info(0);
37 dinfo->type = DATA_RANGE;
38 dinfo->value_ranges = NULL;
39 state = __alloc_smatch_state(0);
40 state->data = dinfo;
41 return state;
44 static struct smatch_state *alloc_extra_state_no_name(int val)
46 struct smatch_state *state;
48 state = __alloc_smatch_state(0);
49 state->data = (void *)alloc_dinfo_range(val, val);
50 return state;
53 /* We do this because ->value_ranges is a list */
54 struct smatch_state *extra_undefined()
56 struct data_info *dinfo;
57 static struct smatch_state *ret;
58 static struct symbol *prev_func;
60 if (prev_func == cur_func)
61 return ret;
62 prev_func = cur_func;
64 dinfo = alloc_dinfo_range(whole_range.min, whole_range.max);
65 ret = __alloc_smatch_state(0);
66 ret->name = "unknown";
67 ret->data = dinfo;
68 return ret;
71 struct smatch_state *alloc_extra_state(int val)
73 struct smatch_state *state;
75 state = alloc_extra_state_no_name(val);
76 state->name = show_ranges(((struct data_info *)state->data)->value_ranges);
77 return state;
80 struct smatch_state *alloc_extra_state_range(long long min, long long max)
82 struct smatch_state *state;
84 if (min == whole_range.min && max == whole_range.max)
85 return extra_undefined();
86 state = __alloc_smatch_state(0);
87 state->data = (void *)alloc_dinfo_range(min, max);
88 state->name = show_ranges(((struct data_info *)state->data)->value_ranges);
89 return state;
92 struct smatch_state *alloc_extra_state_range_list(struct range_list *rl)
94 struct smatch_state *state;
96 state = __alloc_smatch_state(0);
97 state->data = (void *)alloc_dinfo_range_list(rl);
98 state->name = show_ranges(((struct data_info *)state->data)->value_ranges);
99 return state;
102 struct smatch_state *filter_range(struct smatch_state *orig,
103 long long filter_min, long long filter_max)
105 struct smatch_state *ret;
106 struct data_info *orig_info;
107 struct data_info *ret_info;
109 if (!orig)
110 orig = extra_undefined();
111 orig_info = (struct data_info *)orig->data;
112 ret = alloc_extra_state_empty();
113 ret_info = (struct data_info *)ret->data;
114 ret_info->value_ranges = remove_range(orig_info->value_ranges, filter_min, filter_max);
115 ret->name = show_ranges(ret_info->value_ranges);
116 return ret;
119 struct smatch_state *add_filter(struct smatch_state *orig, long long num)
121 return filter_range(orig, num, num);
124 static struct smatch_state *merge_func(const char *name, struct symbol *sym,
125 struct smatch_state *s1,
126 struct smatch_state *s2)
128 struct data_info *info1 = (struct data_info *)s1->data;
129 struct data_info *info2 = (struct data_info *)s2->data;
130 struct data_info *ret_info;
131 struct smatch_state *tmp;
132 struct range_list *value_ranges;
134 value_ranges = range_list_union(info1->value_ranges, info2->value_ranges);
135 tmp = alloc_extra_state_empty();
136 ret_info = (struct data_info *)tmp->data;
137 ret_info->value_ranges = value_ranges;
138 tmp->name = show_ranges(ret_info->value_ranges);
139 return tmp;
142 struct sm_state *__extra_pre_loop_hook_before(struct statement *iterator_pre_statement)
144 struct expression *expr;
145 char *name;
146 struct symbol *sym;
147 struct sm_state *ret = NULL;
149 if (!iterator_pre_statement)
150 return NULL;
151 if (iterator_pre_statement->type != STMT_EXPRESSION)
152 return NULL;
153 expr = iterator_pre_statement->expression;
154 if (expr->type != EXPR_ASSIGNMENT)
155 return NULL;
156 name = get_variable_from_expr(expr->left, &sym);
157 if (!name || !sym)
158 goto free;
159 ret = get_sm_state(my_id, name, sym);
160 free:
161 free_string(name);
162 return ret;
165 static const char *get_iter_op(struct expression *expr)
167 if (expr->type != EXPR_POSTOP && expr->type != EXPR_PREOP)
168 return NULL;
169 return show_special(expr->op);
172 int __iterator_unchanged(struct sm_state *sm, struct statement *iterator)
174 struct expression *iter_expr;
175 const char *op;
176 char *name;
177 struct symbol *sym;
178 int ret = 0;
180 if (!iterator)
181 return 0;
182 if (iterator->type != STMT_EXPRESSION)
183 return 0;
184 iter_expr = iterator->expression;
185 op = get_iter_op(iter_expr);
186 if (!op || (strcmp(op, "--") && strcmp(op, "++")))
187 return 0;
188 name = get_variable_from_expr(iter_expr->unop, &sym);
189 if (!name || !sym)
190 goto free;
191 if (get_sm_state(my_id, name, sym) == sm)
192 ret = 1;
193 free:
194 free_string(name);
195 return ret;
198 void __extra_pre_loop_hook_after(struct sm_state *sm,
199 struct statement *iterator,
200 struct expression *condition)
202 struct expression *iter_expr;
203 char *name;
204 struct symbol *sym;
205 long long value;
206 int left = 0;
207 const char *op;
208 struct smatch_state *state;
209 struct data_info *dinfo;
210 long long min, max;
212 iter_expr = iterator->expression;
214 if (condition->type != EXPR_COMPARE)
215 return;
216 if (!get_value(condition->left, &value)) {
217 if (!get_value(condition->right, &value))
218 return;
219 left = 1;
221 if (left)
222 name = get_variable_from_expr(condition->left, &sym);
223 else
224 name = get_variable_from_expr(condition->right, &sym);
225 if (!name || !sym)
226 goto free;
227 if (sym != sm->sym || strcmp(name, sm->name))
228 goto free;
229 op = get_iter_op(iter_expr);
230 state = get_state(my_id, name, sym);
231 dinfo = (struct data_info *)state->data;
232 min = get_dinfo_min(dinfo);
233 max = get_dinfo_max(dinfo);
234 if (!strcmp(op, "++") && min != whole_range.min && max == whole_range.max) {
235 set_state(my_id, name, sym, alloc_extra_state(min));
236 } else if (min == whole_range.min && max != whole_range.max) {
237 set_state(my_id, name, sym, alloc_extra_state(max));
239 free:
240 free_string(name);
241 return;
244 static struct smatch_state *unmatched_state(struct sm_state *sm)
246 return extra_undefined();
249 static void match_function_call(struct expression *expr)
251 struct expression *tmp;
252 struct symbol *sym;
253 char *name;
254 int i = 0;
256 FOR_EACH_PTR(expr->args, tmp) {
257 if (tmp->op == '&') {
258 name = get_variable_from_expr(tmp->unop, &sym);
259 if (name) {
260 set_state(my_id, name, sym, extra_undefined());
262 free_string(name);
264 i++;
265 } END_FOR_EACH_PTR(tmp);
268 static void match_assign(struct expression *expr)
270 struct expression *left;
271 struct symbol *sym;
272 char *name;
273 long long value;
274 int known;
275 long long min = whole_range.min;
276 long long max = whole_range.max;
277 long long tmp;
279 left = strip_expr(expr->left);
280 name = get_variable_from_expr(left, &sym);
281 if (!name)
282 return;
283 known = get_value(expr->right, &value);
285 if (expr->op == '=') {
286 if (known)
287 set_state(my_id, name, sym, alloc_extra_state(value));
288 else
289 set_state(my_id, name, sym, extra_undefined());
290 goto free;
292 if (expr->op == SPECIAL_ADD_ASSIGN) {
293 if (get_implied_min(expr->unop, &tmp)) {
294 if (known)
295 min = tmp + value;
296 else
297 min = tmp;
301 if (expr->op == SPECIAL_SUB_ASSIGN) {
302 if (get_implied_max(expr->unop, &tmp)) {
303 if (known)
304 max = tmp - value;
305 else
306 max = tmp;
310 set_state(my_id, name, sym, alloc_extra_state_range(min, max));
311 free:
312 free_string(name);
315 static void undef_expr(struct expression *expr)
317 struct symbol *sym;
318 char *name;
319 long long min = whole_range.min;
320 long long max = whole_range.max;
321 long long val;
323 if (expr->op == '*')
324 return;
325 if (expr->op == '(')
326 return;
328 name = get_variable_from_expr(expr->unop, &sym);
329 if (!name)
330 goto free;
331 if (!strcmp("++", show_special(expr->op))) {
332 if (get_implied_min(expr->unop, &val))
333 min = val + 1;
335 if (!strcmp("--", show_special(expr->op))) {
336 if (get_implied_max(expr->unop, &val))
337 max = val - 1;
339 set_state(my_id, name, sym, alloc_extra_state_range(min, max));
340 free:
341 free_string(name);
344 static void match_declarations(struct symbol *sym)
346 const char *name;
347 long long val;
349 if (sym->ident) {
350 name = sym->ident->name;
351 if (sym->initializer) {
352 if (get_value(sym->initializer, &val))
353 set_state(my_id, name, sym, alloc_extra_state(val));
354 else
355 set_state(my_id, name, sym, extra_undefined());
356 scoped_state(name, my_id, sym);
357 } else {
358 set_state(my_id, name, sym, extra_undefined());
359 scoped_state(name, my_id, sym);
364 static void match_function_def(struct symbol *sym)
366 struct symbol *arg;
368 cur_func = sym;
369 FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
370 if (!arg->ident) {
371 continue;
373 set_state(my_id, arg->ident->name, arg, extra_undefined());
374 } END_FOR_EACH_PTR(arg);
377 #define VAL_SINGLE 0
378 #define VAL_MAX 1
379 #define VAL_MIN 2
381 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
383 struct smatch_state *state;
384 struct symbol *sym;
385 char *name;
387 if (get_value(expr, val))
388 return 1;
390 name = get_variable_from_expr(expr, &sym);
391 if (!name)
392 return 0;
393 state = get_state(my_id, name, sym);
394 free_string(name);
395 if (!state || !state->data)
396 return 0;
397 if (what == VAL_SINGLE)
398 return get_single_value_from_range((struct data_info *)state->data, val);
399 if (what == VAL_MAX) {
400 *val = get_dinfo_max((struct data_info *)state->data);
401 if (*val == whole_range.max) /* this means just guessing */
402 return 0;
403 return 1;
405 *val = get_dinfo_min((struct data_info *)state->data);
406 if (*val == whole_range.min)
407 return 0;
408 return 1;
411 int get_implied_single_val(struct expression *expr, long long *val)
413 return get_implied_value_helper(expr, val, VAL_SINGLE);
416 int get_implied_max(struct expression *expr, long long *val)
418 return get_implied_value_helper(expr, val, VAL_MAX);
421 int get_implied_min(struct expression *expr, long long *val)
423 return get_implied_value_helper(expr, val, VAL_MIN);
426 static int last_stmt_val(struct statement *stmt, long long *val)
428 struct expression *expr;
430 if (!stmt)
431 return 0;
433 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
434 if (stmt->type != STMT_EXPRESSION)
435 return 0;
436 expr = stmt->expression;
437 return get_value(expr, val);
440 static void match_comparison(struct expression *expr)
442 long long fixed;
443 char *name = NULL;
444 struct symbol *sym;
445 struct smatch_state *one_state;
446 struct smatch_state *two_state;
447 struct smatch_state *orig;
448 int left = 0;
449 int comparison = expr->op;
450 struct expression *varies = expr->right;
452 if (!get_value(expr->left, &fixed)) {
453 if (!get_value(expr->right, &fixed))
454 return;
455 varies = expr->left;
456 left = 1;
458 if (varies->type == EXPR_PREOP || varies->type == EXPR_POSTOP) {
459 varies = varies->unop;
461 if (varies->type == EXPR_CALL) {
462 function_comparison(comparison, varies, fixed, left);
463 return;
465 name = get_variable_from_expr(varies, &sym);
466 if (!name || !sym)
467 goto free;
469 orig = get_state(my_id, name, sym);
470 if (!orig)
471 orig = extra_undefined();
473 switch(comparison){
474 case '<':
475 case SPECIAL_UNSIGNED_LT:
476 one_state = filter_range(orig, whole_range.min, fixed - 1);
477 two_state = filter_range(orig, fixed, whole_range.max);
478 if (left)
479 set_true_false_states(my_id, name, sym, two_state, one_state);
480 else
481 set_true_false_states(my_id, name, sym, one_state, two_state);
482 return;
483 case SPECIAL_UNSIGNED_LTE:
484 case SPECIAL_LTE:
485 one_state = filter_range(orig, whole_range.min, fixed);
486 two_state = filter_range(orig, fixed + 1, whole_range.max);
487 if (left)
488 set_true_false_states(my_id, name, sym, two_state, one_state);
489 else
490 set_true_false_states(my_id, name, sym, one_state, two_state);
491 return;
492 case SPECIAL_EQUAL:
493 // todo. print a warning here for impossible conditions.
494 one_state = alloc_extra_state(fixed);
495 two_state = filter_range(orig, fixed, fixed);
496 set_true_false_states(my_id, name, sym, one_state, two_state);
497 return;
498 case SPECIAL_UNSIGNED_GTE:
499 case SPECIAL_GTE:
500 one_state = filter_range(orig, whole_range.min, fixed - 1);
501 two_state = filter_range(orig, fixed, whole_range.max);
502 if (left)
503 set_true_false_states(my_id, name, sym, one_state, two_state);
504 else
505 set_true_false_states(my_id, name, sym, two_state, one_state);
506 return;
507 case '>':
508 case SPECIAL_UNSIGNED_GT:
509 one_state = filter_range(orig, whole_range.min, fixed);
510 two_state = filter_range(orig, fixed + 1, whole_range.max);
511 if (left)
512 set_true_false_states(my_id, name, sym, one_state, two_state);
513 else
514 set_true_false_states(my_id, name, sym, two_state, one_state);
515 return;
516 case SPECIAL_NOTEQUAL:
517 one_state = alloc_extra_state(fixed);
518 two_state = filter_range(orig, fixed, fixed);
519 set_true_false_states(my_id, name, sym, two_state, one_state);
520 return;
521 default:
522 sm_msg("unhandled comparison %d\n", comparison);
523 return;
525 return;
526 free:
527 free_string(name);
530 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
531 void __extra_match_condition(struct expression *expr)
533 struct symbol *sym;
534 char *name;
535 struct smatch_state *pre_state;
536 struct smatch_state *true_state;
537 struct smatch_state *false_state;
539 expr = strip_expr(expr);
540 switch(expr->type) {
541 case EXPR_CALL:
542 function_comparison(SPECIAL_NOTEQUAL, expr, 0, 1);
543 return;
544 case EXPR_PREOP:
545 case EXPR_SYMBOL:
546 case EXPR_DEREF:
547 name = get_variable_from_expr(expr, &sym);
548 if (!name)
549 return;
550 pre_state = get_state(my_id, name, sym);
551 true_state = add_filter(pre_state, 0);
552 false_state = alloc_extra_state(0);
553 set_true_false_states(my_id, name, sym, true_state, false_state);
554 free_string(name);
555 return;
556 case EXPR_COMPARE:
557 match_comparison(expr);
558 return;
559 case EXPR_ASSIGNMENT:
560 __extra_match_condition(expr->right);
561 __extra_match_condition(expr->left);
562 return;
566 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
567 int implied_not_equal(struct expression *expr, long long val)
569 char *name;
570 struct symbol *sym;
571 struct smatch_state *state;
572 int ret = 0;
574 name = get_variable_from_expr(expr, &sym);
575 if (!name || !sym)
576 goto exit;
577 state = get_state(my_id, name, sym);
578 if (!state || !state->data)
579 goto exit;
580 ret = !possibly_false(SPECIAL_NOTEQUAL, (struct data_info *)state->data, val, 1);
581 exit:
582 free_string(name);
583 return ret;
586 int known_condition_true(struct expression *expr)
588 long long tmp;
590 if (!expr)
591 return 0;
593 if (get_value(expr, &tmp) && tmp)
594 return 1;
596 expr = strip_expr(expr);
597 switch(expr->type) {
598 case EXPR_PREOP:
599 if (expr->op == '!') {
600 if (known_condition_false(expr->unop))
601 return 1;
602 break;
604 break;
605 default:
606 break;
608 return 0;
611 int known_condition_false(struct expression *expr)
613 if (!expr)
614 return 0;
616 if (is_zero(expr))
617 return 1;
619 switch(expr->type) {
620 case EXPR_PREOP:
621 if (expr->op == '!') {
622 if (known_condition_true(expr->unop))
623 return 1;
624 break;
626 break;
627 default:
628 break;
630 return 0;
633 static int do_comparison_range(struct expression *expr)
635 struct symbol *sym;
636 char *name;
637 struct smatch_state *state;
638 long long value;
639 int left = 0;
640 int poss_true, poss_false;
642 if (!get_value(expr->left, &value)) {
643 if (!get_value(expr->right, &value))
644 return 3;
645 left = 1;
647 if (left)
648 name = get_variable_from_expr(expr->left, &sym);
649 else
650 name = get_variable_from_expr(expr->right, &sym);
651 if (!name || !sym)
652 goto free;
653 state = get_state(SMATCH_EXTRA, name, sym);
654 if (!state)
655 goto free;
656 poss_true = possibly_true(expr->op, (struct data_info *)state->data, value, left);
657 poss_false = possibly_false(expr->op, (struct data_info *)state->data, value, left);
658 if (!poss_true && !poss_false)
659 return 0;
660 if (poss_true && !poss_false)
661 return 1;
662 if (!poss_true && poss_false)
663 return 2;
664 if (poss_true && poss_false)
665 return 3;
666 free:
667 free_string(name);
668 return 3;
671 int implied_condition_true(struct expression *expr)
673 struct statement *stmt;
674 long long tmp;
675 long long val;
677 if (!expr)
678 return 0;
680 if (get_value(expr, &tmp) && tmp)
681 return 1;
683 expr = strip_expr(expr);
684 switch(expr->type) {
685 case EXPR_COMPARE:
686 if (do_comparison_range(expr) == 1)
687 return 1;
688 break;
689 case EXPR_PREOP:
690 if (expr->op == '!') {
691 if (implied_condition_false(expr->unop))
692 return 1;
693 break;
695 stmt = get_block_thing(expr);
696 if (last_stmt_val(stmt, &val) && val == 1)
697 return 1;
698 break;
699 default:
700 if (implied_not_equal(expr, 0) == 1)
701 return 1;
702 break;
704 return 0;
707 int implied_condition_false(struct expression *expr)
709 struct statement *stmt;
710 struct expression *tmp;
711 long long val;
713 if (!expr)
714 return 0;
716 if (is_zero(expr))
717 return 1;
719 switch(expr->type) {
720 case EXPR_COMPARE:
721 if (do_comparison_range(expr) == 2)
722 return 1;
723 case EXPR_PREOP:
724 if (expr->op == '!') {
725 if (implied_condition_true(expr->unop))
726 return 1;
727 break;
729 stmt = get_block_thing(expr);
730 if (last_stmt_val(stmt, &val) && val == 0)
731 return 1;
732 tmp = strip_expr(expr);
733 if (tmp != expr)
734 return implied_condition_false(tmp);
735 break;
736 default:
737 if (get_implied_value(expr, &val) && val == 0)
738 return 1;
739 break;
741 return 0;
744 void register_smatch_extra(int id)
746 my_id = id;
747 add_merge_hook(my_id, &merge_func);
748 add_unmatched_state_hook(my_id, &unmatched_state);
749 add_hook(&undef_expr, OP_HOOK);
750 add_hook(&match_function_def, FUNC_DEF_HOOK);
751 add_hook(&match_function_call, FUNCTION_CALL_HOOK);
752 add_hook(&match_assign, ASSIGNMENT_HOOK);
753 add_hook(&match_declarations, DECLARATION_HOOK);
755 if (option_project == PROJ_KERNEL) {
756 /* I don't know how to test for the ATTRIB_NORET attribute. :( */
757 add_function_hook("panic", &__match_nullify_path_hook, NULL);
758 add_function_hook("do_exit", &__match_nullify_path_hook, NULL);
759 add_function_hook("complete_and_exit", &__match_nullify_path_hook, NULL);
760 add_function_hook("__module_put_and_exit", &__match_nullify_path_hook, NULL);
761 add_function_hook("do_group_exit", &__match_nullify_path_hook, NULL);