&(foo->bar) is not really a dereference.
[smatch.git] / smatch_extra.c
blob45e8bf73e51b097219fed6a30ad0e10d44c0baaa
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 int __iterator_unchanged(struct sm_state *sm, struct statement *iterator)
167 struct expression *iter_expr;
168 char *name;
169 struct symbol *sym;
170 int ret = 0;
172 if (!iterator)
173 return 0;
174 if (iterator->type != STMT_EXPRESSION)
175 return 0;
176 iter_expr = iterator->expression;
177 if (iter_expr->op != SPECIAL_INCREMENT && iter_expr->op != SPECIAL_DECREMENT)
178 return 0;
179 name = get_variable_from_expr(iter_expr->unop, &sym);
180 if (!name || !sym)
181 goto free;
182 if (get_sm_state(my_id, name, sym) == sm)
183 ret = 1;
184 free:
185 free_string(name);
186 return ret;
189 void __extra_pre_loop_hook_after(struct sm_state *sm,
190 struct statement *iterator,
191 struct expression *condition)
193 struct expression *iter_expr;
194 char *name;
195 struct symbol *sym;
196 long long value;
197 int left = 0;
198 struct smatch_state *state;
199 struct data_info *dinfo;
200 long long min, max;
202 iter_expr = iterator->expression;
204 if (condition->type != EXPR_COMPARE)
205 return;
206 if (!get_value(condition->left, &value)) {
207 if (!get_value(condition->right, &value))
208 return;
209 left = 1;
211 if (left)
212 name = get_variable_from_expr(condition->left, &sym);
213 else
214 name = get_variable_from_expr(condition->right, &sym);
215 if (!name || !sym)
216 goto free;
217 if (sym != sm->sym || strcmp(name, sm->name))
218 goto free;
219 state = get_state(my_id, name, sym);
220 dinfo = (struct data_info *)state->data;
221 min = get_dinfo_min(dinfo);
222 max = get_dinfo_max(dinfo);
223 if (iter_expr->op == SPECIAL_INCREMENT && min != whole_range.min && max == whole_range.max) {
224 set_state(my_id, name, sym, alloc_extra_state(min));
225 } else if (min == whole_range.min && max != whole_range.max) {
226 set_state(my_id, name, sym, alloc_extra_state(max));
228 free:
229 free_string(name);
230 return;
233 static struct smatch_state *unmatched_state(struct sm_state *sm)
235 return extra_undefined();
238 static void match_function_call(struct expression *expr)
240 struct expression *tmp;
241 struct symbol *sym;
242 char *name;
243 int i = 0;
245 FOR_EACH_PTR(expr->args, tmp) {
246 if (tmp->op == '&') {
247 name = get_variable_from_expr(tmp->unop, &sym);
248 if (name) {
249 set_state(my_id, name, sym, extra_undefined());
251 free_string(name);
253 i++;
254 } END_FOR_EACH_PTR(tmp);
257 static void match_assign(struct expression *expr)
259 struct expression *left;
260 struct expression *right;
261 struct symbol *sym;
262 char *name;
263 long long value;
264 int known;
265 long long min = whole_range.min;
266 long long max = whole_range.max;
267 long long tmp;
269 left = strip_expr(expr->left);
270 name = get_variable_from_expr(left, &sym);
271 if (!name)
272 return;
273 right = strip_expr(expr->right);
274 while (right->type == EXPR_ASSIGNMENT && right->op == '=')
275 right = strip_expr(right->left);
276 known = get_implied_value(right, &value);
278 if (expr->op == '=') {
279 if (known)
280 set_state(my_id, name, sym, alloc_extra_state(value));
281 else
282 set_state(my_id, name, sym, extra_undefined());
283 goto free;
285 if (expr->op == SPECIAL_ADD_ASSIGN) {
286 if (get_implied_min(left, &tmp)) {
287 if (known)
288 min = tmp + value;
289 else
290 min = tmp;
294 if (expr->op == SPECIAL_SUB_ASSIGN) {
295 if (get_implied_max(left, &tmp)) {
296 if (known)
297 max = tmp - value;
298 else
299 max = tmp;
303 set_state(my_id, name, sym, alloc_extra_state_range(min, max));
304 free:
305 free_string(name);
308 static void unop_expr(struct expression *expr)
310 struct symbol *sym;
311 char *name;
312 long long min = whole_range.min;
313 long long max = whole_range.max;
314 long long val;
316 if (expr->op == '*')
317 return;
318 if (expr->op == '(')
319 return;
321 name = get_variable_from_expr(expr->unop, &sym);
322 if (!name)
323 goto free;
324 if (expr->op == SPECIAL_INCREMENT) {
325 if (get_implied_min(expr->unop, &val))
326 min = val + 1;
328 if (expr->op == SPECIAL_DECREMENT) {
329 if (get_implied_max(expr->unop, &val))
330 max = val - 1;
332 set_state(my_id, name, sym, alloc_extra_state_range(min, max));
333 free:
334 free_string(name);
337 static void match_declarations(struct symbol *sym)
339 const char *name;
340 long long val;
342 if (sym->ident) {
343 name = sym->ident->name;
344 if (sym->initializer) {
345 if (get_value(sym->initializer, &val))
346 set_state(my_id, name, sym, alloc_extra_state(val));
347 else
348 set_state(my_id, name, sym, extra_undefined());
349 scoped_state(my_id, name, sym);
350 } else {
351 set_state(my_id, name, sym, extra_undefined());
352 scoped_state(my_id, name, sym);
357 static void match_function_def(struct symbol *sym)
359 struct symbol *arg;
361 cur_func = sym;
362 FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
363 if (!arg->ident) {
364 continue;
366 set_state(my_id, arg->ident->name, arg, extra_undefined());
367 } END_FOR_EACH_PTR(arg);
370 #define VAL_SINGLE 0
371 #define VAL_MAX 1
372 #define VAL_MIN 2
374 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
376 struct smatch_state *state;
377 struct symbol *sym;
378 char *name;
380 if (get_value(expr, val))
381 return 1;
383 name = get_variable_from_expr(expr, &sym);
384 if (!name)
385 return 0;
386 state = get_state(my_id, name, sym);
387 free_string(name);
388 if (!state || !state->data)
389 return 0;
390 if (what == VAL_SINGLE)
391 return get_single_value_from_range((struct data_info *)state->data, val);
392 if (what == VAL_MAX) {
393 *val = get_dinfo_max((struct data_info *)state->data);
394 if (*val == whole_range.max) /* this means just guessing */
395 return 0;
396 return 1;
398 *val = get_dinfo_min((struct data_info *)state->data);
399 if (*val == whole_range.min)
400 return 0;
401 return 1;
404 int get_implied_single_val(struct expression *expr, long long *val)
406 return get_implied_value_helper(expr, val, VAL_SINGLE);
409 int get_implied_max(struct expression *expr, long long *val)
411 return get_implied_value_helper(expr, val, VAL_MAX);
414 int get_implied_min(struct expression *expr, long long *val)
416 return get_implied_value_helper(expr, val, VAL_MIN);
419 static int last_stmt_val(struct statement *stmt, long long *val)
421 struct expression *expr;
423 if (!stmt)
424 return 0;
426 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
427 if (stmt->type != STMT_EXPRESSION)
428 return 0;
429 expr = stmt->expression;
430 return get_value(expr, val);
433 static void match_comparison(struct expression *expr)
435 long long fixed;
436 char *name = NULL;
437 struct symbol *sym;
438 struct smatch_state *one_state;
439 struct smatch_state *two_state;
440 struct smatch_state *orig;
441 int left = 0;
442 int comparison = expr->op;
443 struct expression *varies = expr->right;
445 if (!get_value(expr->left, &fixed)) {
446 if (!get_value(expr->right, &fixed))
447 return;
448 varies = expr->left;
449 left = 1;
451 if (varies->op == SPECIAL_INCREMENT || varies->op == SPECIAL_DECREMENT)
452 varies = varies->unop;
453 if (varies->type == EXPR_CALL) {
454 function_comparison(comparison, varies, fixed, left);
455 return;
458 name = get_variable_from_expr(varies, &sym);
459 if (!name || !sym)
460 goto free;
462 orig = get_state(my_id, name, sym);
463 if (!orig)
464 orig = extra_undefined();
466 switch(comparison){
467 case '<':
468 case SPECIAL_UNSIGNED_LT:
469 one_state = filter_range(orig, whole_range.min, fixed - 1);
470 two_state = filter_range(orig, fixed, whole_range.max);
471 if (left)
472 set_true_false_states(my_id, name, sym, two_state, one_state);
473 else
474 set_true_false_states(my_id, name, sym, one_state, two_state);
475 return;
476 case SPECIAL_UNSIGNED_LTE:
477 case SPECIAL_LTE:
478 one_state = filter_range(orig, whole_range.min, fixed);
479 two_state = filter_range(orig, fixed + 1, whole_range.max);
480 if (left)
481 set_true_false_states(my_id, name, sym, two_state, one_state);
482 else
483 set_true_false_states(my_id, name, sym, one_state, two_state);
484 return;
485 case SPECIAL_EQUAL:
486 // todo. print a warning here for impossible conditions.
487 one_state = alloc_extra_state(fixed);
488 two_state = filter_range(orig, fixed, fixed);
489 set_true_false_states(my_id, name, sym, one_state, two_state);
490 return;
491 case SPECIAL_UNSIGNED_GTE:
492 case SPECIAL_GTE:
493 one_state = filter_range(orig, whole_range.min, fixed - 1);
494 two_state = filter_range(orig, fixed, whole_range.max);
495 if (left)
496 set_true_false_states(my_id, name, sym, one_state, two_state);
497 else
498 set_true_false_states(my_id, name, sym, two_state, one_state);
499 return;
500 case '>':
501 case SPECIAL_UNSIGNED_GT:
502 one_state = filter_range(orig, whole_range.min, fixed);
503 two_state = filter_range(orig, fixed + 1, whole_range.max);
504 if (left)
505 set_true_false_states(my_id, name, sym, one_state, two_state);
506 else
507 set_true_false_states(my_id, name, sym, two_state, one_state);
508 return;
509 case SPECIAL_NOTEQUAL:
510 one_state = alloc_extra_state(fixed);
511 two_state = filter_range(orig, fixed, fixed);
512 set_true_false_states(my_id, name, sym, two_state, one_state);
513 return;
514 default:
515 sm_msg("unhandled comparison %d\n", comparison);
516 return;
518 return;
519 free:
520 free_string(name);
523 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
524 void __extra_match_condition(struct expression *expr)
526 struct symbol *sym;
527 char *name;
528 struct smatch_state *pre_state;
529 struct smatch_state *true_state;
530 struct smatch_state *false_state;
532 expr = strip_expr(expr);
533 switch(expr->type) {
534 case EXPR_CALL:
535 function_comparison(SPECIAL_NOTEQUAL, expr, 0, 1);
536 return;
537 case EXPR_PREOP:
538 case EXPR_SYMBOL:
539 case EXPR_DEREF:
540 name = get_variable_from_expr(expr, &sym);
541 if (!name)
542 return;
543 pre_state = get_state(my_id, name, sym);
544 true_state = add_filter(pre_state, 0);
545 false_state = alloc_extra_state(0);
546 set_true_false_states(my_id, name, sym, true_state, false_state);
547 free_string(name);
548 return;
549 case EXPR_COMPARE:
550 match_comparison(expr);
551 return;
552 case EXPR_ASSIGNMENT:
553 __extra_match_condition(expr->left);
554 return;
558 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
559 int implied_not_equal(struct expression *expr, long long val)
561 char *name;
562 struct symbol *sym;
563 struct smatch_state *state;
564 int ret = 0;
566 name = get_variable_from_expr(expr, &sym);
567 if (!name || !sym)
568 goto exit;
569 state = get_state(my_id, name, sym);
570 if (!state || !state->data)
571 goto exit;
572 ret = !possibly_false(SPECIAL_NOTEQUAL, (struct data_info *)state->data, val, 1);
573 exit:
574 free_string(name);
575 return ret;
578 int known_condition_true(struct expression *expr)
580 long long tmp;
582 if (!expr)
583 return 0;
585 if (get_value(expr, &tmp) && tmp)
586 return 1;
588 expr = strip_expr(expr);
589 switch(expr->type) {
590 case EXPR_PREOP:
591 if (expr->op == '!') {
592 if (known_condition_false(expr->unop))
593 return 1;
594 break;
596 break;
597 default:
598 break;
600 return 0;
603 int known_condition_false(struct expression *expr)
605 if (!expr)
606 return 0;
608 if (is_zero(expr))
609 return 1;
611 switch(expr->type) {
612 case EXPR_PREOP:
613 if (expr->op == '!') {
614 if (known_condition_true(expr->unop))
615 return 1;
616 break;
618 break;
619 default:
620 break;
622 return 0;
625 static int do_comparison_range(struct expression *expr)
627 struct symbol *sym;
628 char *name;
629 struct smatch_state *state;
630 long long value;
631 int left = 0;
632 int poss_true, poss_false;
634 if (!get_value(expr->left, &value)) {
635 if (!get_value(expr->right, &value))
636 return 3;
637 left = 1;
639 if (left)
640 name = get_variable_from_expr(expr->left, &sym);
641 else
642 name = get_variable_from_expr(expr->right, &sym);
643 if (!name || !sym)
644 goto free;
645 state = get_state(SMATCH_EXTRA, name, sym);
646 if (!state)
647 goto free;
648 poss_true = possibly_true(expr->op, (struct data_info *)state->data, value, left);
649 poss_false = possibly_false(expr->op, (struct data_info *)state->data, value, left);
650 if (!poss_true && !poss_false)
651 return 0;
652 if (poss_true && !poss_false)
653 return 1;
654 if (!poss_true && poss_false)
655 return 2;
656 if (poss_true && poss_false)
657 return 3;
658 free:
659 free_string(name);
660 return 3;
663 int implied_condition_true(struct expression *expr)
665 struct statement *stmt;
666 long long tmp;
667 long long val;
669 if (!expr)
670 return 0;
672 if (get_value(expr, &tmp) && tmp)
673 return 1;
675 expr = strip_expr(expr);
676 switch(expr->type) {
677 case EXPR_COMPARE:
678 if (do_comparison_range(expr) == 1)
679 return 1;
680 break;
681 case EXPR_PREOP:
682 if (expr->op == '!') {
683 if (implied_condition_false(expr->unop))
684 return 1;
685 break;
687 stmt = get_block_thing(expr);
688 if (last_stmt_val(stmt, &val) && val == 1)
689 return 1;
690 break;
691 default:
692 if (implied_not_equal(expr, 0) == 1)
693 return 1;
694 break;
696 return 0;
699 int implied_condition_false(struct expression *expr)
701 struct statement *stmt;
702 struct expression *tmp;
703 long long val;
705 if (!expr)
706 return 0;
708 if (is_zero(expr))
709 return 1;
711 switch(expr->type) {
712 case EXPR_COMPARE:
713 if (do_comparison_range(expr) == 2)
714 return 1;
715 case EXPR_PREOP:
716 if (expr->op == '!') {
717 if (implied_condition_true(expr->unop))
718 return 1;
719 break;
721 stmt = get_block_thing(expr);
722 if (last_stmt_val(stmt, &val) && val == 0)
723 return 1;
724 tmp = strip_expr(expr);
725 if (tmp != expr)
726 return implied_condition_false(tmp);
727 break;
728 default:
729 if (get_implied_value(expr, &val) && val == 0)
730 return 1;
731 break;
733 return 0;
736 void register_smatch_extra(int id)
738 my_id = id;
739 add_merge_hook(my_id, &merge_func);
740 add_unmatched_state_hook(my_id, &unmatched_state);
741 add_hook(&unop_expr, OP_HOOK);
742 add_hook(&match_function_def, FUNC_DEF_HOOK);
743 add_hook(&match_function_call, FUNCTION_CALL_HOOK);
744 add_hook(&match_assign, ASSIGNMENT_HOOK);
745 add_hook(&match_declarations, DECLARATION_HOOK);
747 if (option_project == PROJ_KERNEL) {
748 /* I don't know how to test for the ATTRIB_NORET attribute. :( */
749 add_function_hook("panic", &__match_nullify_path_hook, NULL);
750 add_function_hook("do_exit", &__match_nullify_path_hook, NULL);
751 add_function_hook("complete_and_exit", &__match_nullify_path_hook, NULL);
752 add_function_hook("__module_put_and_exit", &__match_nullify_path_hook, NULL);
753 add_function_hook("do_group_exit", &__match_nullify_path_hook, NULL);