exit and ExitProcess don't return
[smatch.git] / smatch_extra.c
blob579c294ab451b8871a62b92e1eb1d85a1b7e913d
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 symbol *sym;
261 char *name;
262 long long value;
263 int known;
264 long long min = whole_range.min;
265 long long max = whole_range.max;
266 long long tmp;
268 left = strip_expr(expr->left);
269 name = get_variable_from_expr(left, &sym);
270 if (!name)
271 return;
272 known = get_value(expr->right, &value);
274 if (expr->op == '=') {
275 if (known)
276 set_state(my_id, name, sym, alloc_extra_state(value));
277 else
278 set_state(my_id, name, sym, extra_undefined());
279 goto free;
281 if (expr->op == SPECIAL_ADD_ASSIGN) {
282 if (get_implied_min(expr->unop, &tmp)) {
283 if (known)
284 min = tmp + value;
285 else
286 min = tmp;
290 if (expr->op == SPECIAL_SUB_ASSIGN) {
291 if (get_implied_max(expr->unop, &tmp)) {
292 if (known)
293 max = tmp - value;
294 else
295 max = tmp;
299 set_state(my_id, name, sym, alloc_extra_state_range(min, max));
300 free:
301 free_string(name);
304 static void undef_expr(struct expression *expr)
306 struct symbol *sym;
307 char *name;
308 long long min = whole_range.min;
309 long long max = whole_range.max;
310 long long val;
312 if (expr->op == '*')
313 return;
314 if (expr->op == '(')
315 return;
317 name = get_variable_from_expr(expr->unop, &sym);
318 if (!name)
319 goto free;
320 if (expr->op == SPECIAL_INCREMENT) {
321 if (get_implied_min(expr->unop, &val))
322 min = val + 1;
324 if (expr->op == SPECIAL_DECREMENT) {
325 if (get_implied_max(expr->unop, &val))
326 max = val - 1;
328 set_state(my_id, name, sym, alloc_extra_state_range(min, max));
329 free:
330 free_string(name);
333 static void match_declarations(struct symbol *sym)
335 const char *name;
336 long long val;
338 if (sym->ident) {
339 name = sym->ident->name;
340 if (sym->initializer) {
341 if (get_value(sym->initializer, &val))
342 set_state(my_id, name, sym, alloc_extra_state(val));
343 else
344 set_state(my_id, name, sym, extra_undefined());
345 scoped_state(name, my_id, sym);
346 } else {
347 set_state(my_id, name, sym, extra_undefined());
348 scoped_state(name, my_id, sym);
353 static void match_function_def(struct symbol *sym)
355 struct symbol *arg;
357 cur_func = sym;
358 FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
359 if (!arg->ident) {
360 continue;
362 set_state(my_id, arg->ident->name, arg, extra_undefined());
363 } END_FOR_EACH_PTR(arg);
366 #define VAL_SINGLE 0
367 #define VAL_MAX 1
368 #define VAL_MIN 2
370 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
372 struct smatch_state *state;
373 struct symbol *sym;
374 char *name;
376 if (get_value(expr, val))
377 return 1;
379 name = get_variable_from_expr(expr, &sym);
380 if (!name)
381 return 0;
382 state = get_state(my_id, name, sym);
383 free_string(name);
384 if (!state || !state->data)
385 return 0;
386 if (what == VAL_SINGLE)
387 return get_single_value_from_range((struct data_info *)state->data, val);
388 if (what == VAL_MAX) {
389 *val = get_dinfo_max((struct data_info *)state->data);
390 if (*val == whole_range.max) /* this means just guessing */
391 return 0;
392 return 1;
394 *val = get_dinfo_min((struct data_info *)state->data);
395 if (*val == whole_range.min)
396 return 0;
397 return 1;
400 int get_implied_single_val(struct expression *expr, long long *val)
402 return get_implied_value_helper(expr, val, VAL_SINGLE);
405 int get_implied_max(struct expression *expr, long long *val)
407 return get_implied_value_helper(expr, val, VAL_MAX);
410 int get_implied_min(struct expression *expr, long long *val)
412 return get_implied_value_helper(expr, val, VAL_MIN);
415 static int last_stmt_val(struct statement *stmt, long long *val)
417 struct expression *expr;
419 if (!stmt)
420 return 0;
422 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
423 if (stmt->type != STMT_EXPRESSION)
424 return 0;
425 expr = stmt->expression;
426 return get_value(expr, val);
429 static void match_comparison(struct expression *expr)
431 long long fixed;
432 char *name = NULL;
433 struct symbol *sym;
434 struct smatch_state *one_state;
435 struct smatch_state *two_state;
436 struct smatch_state *orig;
437 int left = 0;
438 int comparison = expr->op;
439 struct expression *varies = expr->right;
441 if (!get_value(expr->left, &fixed)) {
442 if (!get_value(expr->right, &fixed))
443 return;
444 varies = expr->left;
445 left = 1;
447 if (varies->type == EXPR_PREOP || varies->type == EXPR_POSTOP) {
448 varies = varies->unop;
450 if (varies->type == EXPR_CALL) {
451 function_comparison(comparison, varies, fixed, left);
452 return;
454 name = get_variable_from_expr(varies, &sym);
455 if (!name || !sym)
456 goto free;
458 orig = get_state(my_id, name, sym);
459 if (!orig)
460 orig = extra_undefined();
462 switch(comparison){
463 case '<':
464 case SPECIAL_UNSIGNED_LT:
465 one_state = filter_range(orig, whole_range.min, fixed - 1);
466 two_state = filter_range(orig, fixed, whole_range.max);
467 if (left)
468 set_true_false_states(my_id, name, sym, two_state, one_state);
469 else
470 set_true_false_states(my_id, name, sym, one_state, two_state);
471 return;
472 case SPECIAL_UNSIGNED_LTE:
473 case SPECIAL_LTE:
474 one_state = filter_range(orig, whole_range.min, fixed);
475 two_state = filter_range(orig, fixed + 1, whole_range.max);
476 if (left)
477 set_true_false_states(my_id, name, sym, two_state, one_state);
478 else
479 set_true_false_states(my_id, name, sym, one_state, two_state);
480 return;
481 case SPECIAL_EQUAL:
482 // todo. print a warning here for impossible conditions.
483 one_state = alloc_extra_state(fixed);
484 two_state = filter_range(orig, fixed, fixed);
485 set_true_false_states(my_id, name, sym, one_state, two_state);
486 return;
487 case SPECIAL_UNSIGNED_GTE:
488 case SPECIAL_GTE:
489 one_state = filter_range(orig, whole_range.min, fixed - 1);
490 two_state = filter_range(orig, fixed, whole_range.max);
491 if (left)
492 set_true_false_states(my_id, name, sym, one_state, two_state);
493 else
494 set_true_false_states(my_id, name, sym, two_state, one_state);
495 return;
496 case '>':
497 case SPECIAL_UNSIGNED_GT:
498 one_state = filter_range(orig, whole_range.min, fixed);
499 two_state = filter_range(orig, fixed + 1, whole_range.max);
500 if (left)
501 set_true_false_states(my_id, name, sym, one_state, two_state);
502 else
503 set_true_false_states(my_id, name, sym, two_state, one_state);
504 return;
505 case SPECIAL_NOTEQUAL:
506 one_state = alloc_extra_state(fixed);
507 two_state = filter_range(orig, fixed, fixed);
508 set_true_false_states(my_id, name, sym, two_state, one_state);
509 return;
510 default:
511 sm_msg("unhandled comparison %d\n", comparison);
512 return;
514 return;
515 free:
516 free_string(name);
519 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
520 void __extra_match_condition(struct expression *expr)
522 struct symbol *sym;
523 char *name;
524 struct smatch_state *pre_state;
525 struct smatch_state *true_state;
526 struct smatch_state *false_state;
528 expr = strip_expr(expr);
529 switch(expr->type) {
530 case EXPR_CALL:
531 function_comparison(SPECIAL_NOTEQUAL, expr, 0, 1);
532 return;
533 case EXPR_PREOP:
534 case EXPR_SYMBOL:
535 case EXPR_DEREF:
536 name = get_variable_from_expr(expr, &sym);
537 if (!name)
538 return;
539 pre_state = get_state(my_id, name, sym);
540 true_state = add_filter(pre_state, 0);
541 false_state = alloc_extra_state(0);
542 set_true_false_states(my_id, name, sym, true_state, false_state);
543 free_string(name);
544 return;
545 case EXPR_COMPARE:
546 match_comparison(expr);
547 return;
548 case EXPR_ASSIGNMENT:
549 __extra_match_condition(expr->right);
550 __extra_match_condition(expr->left);
551 return;
555 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
556 int implied_not_equal(struct expression *expr, long long val)
558 char *name;
559 struct symbol *sym;
560 struct smatch_state *state;
561 int ret = 0;
563 name = get_variable_from_expr(expr, &sym);
564 if (!name || !sym)
565 goto exit;
566 state = get_state(my_id, name, sym);
567 if (!state || !state->data)
568 goto exit;
569 ret = !possibly_false(SPECIAL_NOTEQUAL, (struct data_info *)state->data, val, 1);
570 exit:
571 free_string(name);
572 return ret;
575 int known_condition_true(struct expression *expr)
577 long long tmp;
579 if (!expr)
580 return 0;
582 if (get_value(expr, &tmp) && tmp)
583 return 1;
585 expr = strip_expr(expr);
586 switch(expr->type) {
587 case EXPR_PREOP:
588 if (expr->op == '!') {
589 if (known_condition_false(expr->unop))
590 return 1;
591 break;
593 break;
594 default:
595 break;
597 return 0;
600 int known_condition_false(struct expression *expr)
602 if (!expr)
603 return 0;
605 if (is_zero(expr))
606 return 1;
608 switch(expr->type) {
609 case EXPR_PREOP:
610 if (expr->op == '!') {
611 if (known_condition_true(expr->unop))
612 return 1;
613 break;
615 break;
616 default:
617 break;
619 return 0;
622 static int do_comparison_range(struct expression *expr)
624 struct symbol *sym;
625 char *name;
626 struct smatch_state *state;
627 long long value;
628 int left = 0;
629 int poss_true, poss_false;
631 if (!get_value(expr->left, &value)) {
632 if (!get_value(expr->right, &value))
633 return 3;
634 left = 1;
636 if (left)
637 name = get_variable_from_expr(expr->left, &sym);
638 else
639 name = get_variable_from_expr(expr->right, &sym);
640 if (!name || !sym)
641 goto free;
642 state = get_state(SMATCH_EXTRA, name, sym);
643 if (!state)
644 goto free;
645 poss_true = possibly_true(expr->op, (struct data_info *)state->data, value, left);
646 poss_false = possibly_false(expr->op, (struct data_info *)state->data, value, left);
647 if (!poss_true && !poss_false)
648 return 0;
649 if (poss_true && !poss_false)
650 return 1;
651 if (!poss_true && poss_false)
652 return 2;
653 if (poss_true && poss_false)
654 return 3;
655 free:
656 free_string(name);
657 return 3;
660 int implied_condition_true(struct expression *expr)
662 struct statement *stmt;
663 long long tmp;
664 long long val;
666 if (!expr)
667 return 0;
669 if (get_value(expr, &tmp) && tmp)
670 return 1;
672 expr = strip_expr(expr);
673 switch(expr->type) {
674 case EXPR_COMPARE:
675 if (do_comparison_range(expr) == 1)
676 return 1;
677 break;
678 case EXPR_PREOP:
679 if (expr->op == '!') {
680 if (implied_condition_false(expr->unop))
681 return 1;
682 break;
684 stmt = get_block_thing(expr);
685 if (last_stmt_val(stmt, &val) && val == 1)
686 return 1;
687 break;
688 default:
689 if (implied_not_equal(expr, 0) == 1)
690 return 1;
691 break;
693 return 0;
696 int implied_condition_false(struct expression *expr)
698 struct statement *stmt;
699 struct expression *tmp;
700 long long val;
702 if (!expr)
703 return 0;
705 if (is_zero(expr))
706 return 1;
708 switch(expr->type) {
709 case EXPR_COMPARE:
710 if (do_comparison_range(expr) == 2)
711 return 1;
712 case EXPR_PREOP:
713 if (expr->op == '!') {
714 if (implied_condition_true(expr->unop))
715 return 1;
716 break;
718 stmt = get_block_thing(expr);
719 if (last_stmt_val(stmt, &val) && val == 0)
720 return 1;
721 tmp = strip_expr(expr);
722 if (tmp != expr)
723 return implied_condition_false(tmp);
724 break;
725 default:
726 if (get_implied_value(expr, &val) && val == 0)
727 return 1;
728 break;
730 return 0;
733 void register_smatch_extra(int id)
735 my_id = id;
736 add_merge_hook(my_id, &merge_func);
737 add_unmatched_state_hook(my_id, &unmatched_state);
738 add_hook(&undef_expr, OP_HOOK);
739 add_hook(&match_function_def, FUNC_DEF_HOOK);
740 add_hook(&match_function_call, FUNCTION_CALL_HOOK);
741 add_hook(&match_assign, ASSIGNMENT_HOOK);
742 add_hook(&match_declarations, DECLARATION_HOOK);
744 if (option_project == PROJ_KERNEL) {
745 /* I don't know how to test for the ATTRIB_NORET attribute. :( */
746 add_function_hook("panic", &__match_nullify_path_hook, NULL);
747 add_function_hook("do_exit", &__match_nullify_path_hook, NULL);
748 add_function_hook("complete_and_exit", &__match_nullify_path_hook, NULL);
749 add_function_hook("__module_put_and_exit", &__match_nullify_path_hook, NULL);
750 add_function_hook("do_group_exit", &__match_nullify_path_hook, NULL);