Rename smatch_extra_helper.c to smatch_ranges.c
[smatch.git] / smatch_extra.c
bloba2c751bbfcf4fc036dd314a789832e1945e9fee1
1 /*
2 * sparse/smatch_extra.c
4 * Copyright (C) 2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
10 #include <stdlib.h>
11 #define __USE_ISOC99
12 #include <limits.h>
13 #include "parse.h"
14 #include "smatch.h"
15 #include "smatch_slist.h"
16 #include "smatch_extra.h"
18 static int my_id;
20 static struct symbol *cur_func;
22 struct data_range whole_range = {
23 .min = LLONG_MIN,
24 .max = LLONG_MAX,
27 static struct smatch_state *alloc_extra_state_empty()
29 struct smatch_state *state;
30 struct data_info *dinfo;
32 dinfo = __alloc_data_info(0);
33 dinfo->type = DATA_RANGE;
34 dinfo->merged = 0;
35 dinfo->value_ranges = NULL;
36 state = __alloc_smatch_state(0);
37 state->data = dinfo;
38 return state;
41 static struct smatch_state *alloc_extra_state_no_name(int val)
43 struct smatch_state *state;
45 state = __alloc_smatch_state(0);
46 if (val == UNDEFINED)
47 state->data = (void *)alloc_dinfo_range(whole_range.min, whole_range.max);
48 else
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;
72 /* This is like extra_undefined() except merged. */
73 struct smatch_state *min_max_merged()
75 struct data_info *dinfo;
76 static struct smatch_state *ret;
77 static struct symbol *prev_func;
79 if (prev_func == cur_func)
80 return ret;
81 prev_func = cur_func;
83 dinfo = alloc_dinfo_range(whole_range.min, whole_range.max);
84 dinfo->merged = 1;
85 ret = __alloc_smatch_state(0);
86 ret->name = "whole_range";
87 ret->data = dinfo;
88 return ret;
91 struct smatch_state *alloc_extra_state(int val)
93 struct smatch_state *state;
95 if (val == UNDEFINED)
96 return extra_undefined();
97 state = alloc_extra_state_no_name(val);
98 state->name = show_ranges(((struct data_info *)state->data)->value_ranges);
99 return state;
102 struct smatch_state *alloc_extra_state_range(long long min, long long max)
104 struct smatch_state *state;
106 if (min == whole_range.min && max == whole_range.max)
107 return extra_undefined();
108 state = __alloc_smatch_state(0);
109 state->data = (void *)alloc_dinfo_range(min, max);
110 state->name = show_ranges(((struct data_info *)state->data)->value_ranges);
111 return state;
114 struct smatch_state *filter_range(struct smatch_state *orig,
115 long long filter_min, long long filter_max)
117 struct smatch_state *ret;
118 struct data_info *orig_info;
119 struct data_info *ret_info;
121 if (!orig)
122 orig = extra_undefined();
123 orig_info = (struct data_info *)orig->data;
124 ret = alloc_extra_state_empty();
125 ret_info = (struct data_info *)ret->data;
126 ret_info->value_ranges = remove_range(orig_info->value_ranges, filter_min, filter_max);
127 ret->name = show_ranges(ret_info->value_ranges);
128 return ret;
131 struct smatch_state *add_filter(struct smatch_state *orig, long long num)
133 return filter_range(orig, num, num);
136 static struct smatch_state *merge_func(const char *name, struct symbol *sym,
137 struct smatch_state *s1,
138 struct smatch_state *s2)
140 struct data_info *info1 = (struct data_info *)s1->data;
141 struct data_info *info2 = (struct data_info *)s2->data;
142 struct data_info *ret_info;
143 struct smatch_state *tmp;
144 struct range_list *value_ranges;
146 value_ranges = range_list_union(info1->value_ranges, info2->value_ranges);
147 if (is_whole_range(value_ranges))
148 return min_max_merged();
149 tmp = alloc_extra_state_empty();
150 ret_info = (struct data_info *)tmp->data;
151 ret_info->merged = 1;
152 ret_info->value_ranges = value_ranges;
153 tmp->name = show_ranges(ret_info->value_ranges);
154 return tmp;
157 struct sm_state *__extra_merge(struct sm_state *one, struct state_list *slist1,
158 struct sm_state *two, struct state_list *slist2)
160 struct data_info *info1;
161 struct data_info *info2;
163 if (!one->state->data || !two->state->data) {
164 smatch_msg("internal error in smatch extra '%s = %s or %s'",
165 one->name, show_state(one->state),
166 show_state(two->state));
167 return alloc_state(one->name, one->owner, one->sym,
168 extra_undefined());
171 info1 = (struct data_info *)one->state->data;
172 info2 = (struct data_info *)two->state->data;
174 if (!info1->merged)
175 free_stack(&one->my_pools);
176 if (!info2->merged)
177 free_stack(&two->my_pools);
179 if (one == two && !one->my_pools) {
180 add_pool(&one->my_pools, slist1);
181 add_pool(&one->my_pools, slist2);
182 } else {
183 if (!one->my_pools)
184 add_pool(&one->my_pools, slist1);
185 if (!two->my_pools)
186 add_pool(&two->my_pools, slist2);
189 add_pool(&one->all_pools, slist1);
190 add_pool(&two->all_pools, slist2);
191 return merge_sm_states(one, two);
194 struct sm_state *__extra_and_merge(struct sm_state *sm,
195 struct state_list_stack *stack)
197 struct state_list *slist;
198 struct sm_state *ret = NULL;
199 struct sm_state *tmp;
200 int i = 0;
202 FOR_EACH_PTR(stack, slist) {
203 if (!i++) {
204 ret = get_sm_state_slist(slist, sm->name, sm->owner,
205 sm->sym);
206 } else {
207 tmp = get_sm_state_slist(slist, sm->name, sm->owner,
208 sm->sym);
209 ret = merge_sm_states(ret, tmp);
211 } END_FOR_EACH_PTR(slist);
212 if (!ret) {
213 smatch_msg("Internal error in __extra_and_merge");
214 return NULL;
216 ret->my_pools = stack;
217 ret->all_pools = clone_stack(stack);
218 return ret;
221 struct sm_state *__extra_pre_loop_hook_before(struct statement *iterator_pre_statement)
223 struct expression *expr;
224 char *name;
225 struct symbol *sym;
226 struct sm_state *ret = NULL;
228 if (!iterator_pre_statement)
229 return NULL;
230 if (iterator_pre_statement->type != STMT_EXPRESSION)
231 return NULL;
232 expr = iterator_pre_statement->expression;
233 if (expr->type != EXPR_ASSIGNMENT)
234 return NULL;
235 name = get_variable_from_expr(expr->left, &sym);
236 if (!name || !sym)
237 goto free;
238 ret = get_sm_state(name, my_id, sym);
239 free:
240 free_string(name);
241 return ret;
244 static const char *get_iter_op(struct expression *expr)
246 if (expr->type != EXPR_POSTOP && expr->type != EXPR_PREOP)
247 return NULL;
248 return show_special(expr->op);
251 int __iterator_unchanged(struct sm_state *sm, struct statement *iterator)
253 struct expression *iter_expr;
254 const char *op;
255 char *name;
256 struct symbol *sym;
257 int ret = 0;
259 if (!iterator)
260 return 0;
261 if (iterator->type != STMT_EXPRESSION)
262 return 0;
263 iter_expr = iterator->expression;
264 op = get_iter_op(iter_expr);
265 if (!op || (strcmp(op, "--") && strcmp(op, "++")))
266 return 0;
267 name = get_variable_from_expr(iter_expr->unop, &sym);
268 if (!name || !sym)
269 goto free;
270 if (get_sm_state(name, my_id, sym) == sm)
271 ret = 1;
272 free:
273 free_string(name);
274 return ret;
277 void __extra_pre_loop_hook_after(struct sm_state *sm,
278 struct statement *iterator,
279 struct expression *condition)
281 struct expression *iter_expr;
282 char *name;
283 struct symbol *sym;
284 long long value;
285 int left;
286 const char *op;
287 struct smatch_state *state;
288 struct data_info *dinfo;
289 long long min, max;
291 iter_expr = iterator->expression;
293 if (condition->type != EXPR_COMPARE)
294 return;
295 value = get_value(condition->left);
296 if (value == UNDEFINED) {
297 value = get_value(condition->right);
298 if (value == UNDEFINED)
299 return;
300 left = 1;
302 if (left)
303 name = get_variable_from_expr(condition->left, &sym);
304 else
305 name = get_variable_from_expr(condition->right, &sym);
306 if (!name || !sym)
307 goto free;
308 if (sym != sm->sym || strcmp(name, sm->name))
309 goto free;
310 op = get_iter_op(iter_expr);
311 state = get_state(name, my_id, sym);
312 dinfo = (struct data_info *)state->data;
313 min = get_dinfo_min(dinfo);
314 max = get_dinfo_max(dinfo);
315 if (!strcmp(op, "++") && min != whole_range.min && max == whole_range.max) {
316 set_state(name, my_id, sym, alloc_extra_state(min));
317 } else if (min == whole_range.min && max != whole_range.max) {
318 set_state(name, my_id, sym, alloc_extra_state(max));
320 free:
321 free_string(name);
322 return;
325 static struct smatch_state *unmatched_state(struct sm_state *sm)
327 return extra_undefined();
330 static void match_function_call(struct expression *expr)
332 struct expression *tmp;
333 struct symbol *sym;
334 char *name;
335 int i = 0;
337 FOR_EACH_PTR(expr->args, tmp) {
338 if (tmp->op == '&') {
339 name = get_variable_from_expr(tmp->unop, &sym);
340 if (name) {
341 set_state(name, my_id, sym, extra_undefined());
343 free_string(name);
345 i++;
346 } END_FOR_EACH_PTR(tmp);
349 static void match_assign(struct expression *expr)
351 struct expression *left;
352 struct symbol *sym;
353 char *name;
355 left = strip_expr(expr->left);
356 name = get_variable_from_expr(left, &sym);
357 if (!name)
358 return;
359 set_state(name, my_id, sym, alloc_extra_state(get_value(expr->right)));
360 free_string(name);
363 static void undef_expr(struct expression *expr)
365 struct symbol *sym;
366 char *name;
368 name = get_variable_from_expr(expr->unop, &sym);
369 if (!name)
370 return;
371 if (!get_state(name, my_id, sym)) {
372 free_string(name);
373 return;
375 set_state(name, my_id, sym, extra_undefined());
376 free_string(name);
379 static void match_declarations(struct symbol *sym)
381 const char *name;
383 if (sym->ident) {
384 name = sym->ident->name;
385 if (sym->initializer) {
386 set_state(name, my_id, sym, alloc_extra_state(get_value(sym->initializer)));
387 } else {
388 set_state(name, my_id, sym, extra_undefined());
393 static void match_function_def(struct symbol *sym)
395 struct symbol *arg;
397 cur_func = sym;
398 FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
399 if (!arg->ident) {
400 continue;
402 set_state(arg->ident->name, my_id, arg, extra_undefined());
403 } END_FOR_EACH_PTR(arg);
406 static void match_unop(struct expression *expr)
408 struct symbol *sym;
409 char *name;
410 const char *tmp;
413 name = get_variable_from_expr(expr->unop, &sym);
414 if (!name)
415 return;
417 tmp = show_special(expr->op);
418 if ((!strcmp(tmp, "--")) || (!strcmp(tmp, "++")))
419 set_state(name, my_id, sym, extra_undefined());
420 free_string(name);
423 int get_implied_value(struct expression *expr)
425 struct smatch_state *state;
426 int val;
427 struct symbol *sym;
428 char *name;
430 val = get_value(expr);
431 if (val != UNDEFINED)
432 return val;
434 name = get_variable_from_expr(expr, &sym);
435 if (!name)
436 return UNDEFINED;
437 state = get_state(name, my_id, sym);
438 free_string(name);
439 if (!state || !state->data)
440 return UNDEFINED;
441 return get_single_value_from_range((struct data_info *)state->data);
444 int last_stmt_val(struct statement *stmt)
446 struct expression *expr;
448 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
449 if (stmt->type != STMT_EXPRESSION)
450 return UNDEFINED;
451 expr = stmt->expression;
452 return get_value(expr);
455 static void match_comparison(struct expression *expr)
457 long long value;
458 char *name = NULL;
459 struct symbol *sym;
460 struct smatch_state *one_state;
461 struct smatch_state *two_state;
462 struct smatch_state *orig;
463 int left;
464 int comparison = expr->op;
466 value = get_value(expr->left);
467 if (value == UNDEFINED) {
468 value = get_value(expr->right);
469 if (value == UNDEFINED)
470 return;
471 left = 1;
473 if (left)
474 name = get_variable_from_expr(expr->left, &sym);
475 else
476 name = get_variable_from_expr(expr->right, &sym);
477 if (!name || !sym)
478 goto free;
480 orig = get_state(name, my_id, sym);
481 if (!orig)
482 orig = extra_undefined();
484 switch(comparison){
485 case '<':
486 case SPECIAL_UNSIGNED_LT:
487 one_state = filter_range(orig, whole_range.min, value - 1);
488 two_state = filter_range(orig, value, whole_range.max);
489 if (left)
490 set_true_false_states(name, my_id, sym, two_state, one_state);
491 else
492 set_true_false_states(name, my_id, sym, one_state, two_state);
493 return;
494 case SPECIAL_UNSIGNED_LTE:
495 case SPECIAL_LTE:
496 one_state = filter_range(orig, whole_range.min, value);
497 two_state = filter_range(orig, value + 1, whole_range.max);
498 if (left)
499 set_true_false_states(name, my_id, sym, two_state, one_state);
500 else
501 set_true_false_states(name, my_id, sym, one_state, two_state);
502 return;
503 case SPECIAL_EQUAL:
504 // todo. print a warning here for impossible conditions.
505 one_state = alloc_extra_state(value);
506 two_state = filter_range(orig, value, value);
507 set_true_false_states(name, my_id, sym, one_state, two_state);
508 return;
509 case SPECIAL_UNSIGNED_GTE:
510 case SPECIAL_GTE:
511 one_state = filter_range(orig, whole_range.min, value - 1);
512 two_state = filter_range(orig, value, whole_range.max);
513 if (left)
514 set_true_false_states(name, my_id, sym, one_state, two_state);
515 else
516 set_true_false_states(name, my_id, sym, two_state, one_state);
517 return;
518 case '>':
519 case SPECIAL_UNSIGNED_GT:
520 one_state = filter_range(orig, whole_range.min, value);
521 two_state = filter_range(orig, value + 1, whole_range.max);
522 if (left)
523 set_true_false_states(name, my_id, sym, one_state, two_state);
524 else
525 set_true_false_states(name, my_id, sym, two_state, one_state);
526 return;
527 case SPECIAL_NOTEQUAL:
528 one_state = filter_range(orig, value, value);
529 two_state = filter_range(orig, value, value);
530 set_true_false_states(name, my_id, sym, two_state, one_state);
531 return;
532 default:
533 smatch_msg("unhandled comparison %d\n", comparison);
534 return;
536 return;
537 free:
538 free_string(name);
541 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
542 void __extra_match_condition(struct expression *expr)
544 struct symbol *sym;
545 char *name;
546 struct smatch_state *pre_state;
547 struct smatch_state *true_state;
548 struct smatch_state *false_state;
550 expr = strip_expr(expr);
551 switch(expr->type) {
552 case EXPR_PREOP:
553 case EXPR_SYMBOL:
554 case EXPR_DEREF:
555 name = get_variable_from_expr(expr, &sym);
556 if (!name)
557 return;
558 pre_state = get_state(name, my_id, sym);
559 true_state = add_filter(pre_state, 0);
560 false_state = alloc_extra_state(0);
561 set_true_false_states(name, my_id, sym, true_state, false_state);
562 free_string(name);
563 return;
564 case EXPR_COMPARE:
565 match_comparison(expr);
566 return;
570 static int variable_non_zero(struct expression *expr)
572 char *name;
573 struct symbol *sym;
574 struct smatch_state *state;
575 int ret = UNDEFINED;
577 name = get_variable_from_expr(expr, &sym);
578 if (!name || !sym)
579 goto exit;
580 state = get_state(name, my_id, sym);
581 if (!state || !state->data)
582 goto exit;
583 ret = !possibly_false(SPECIAL_NOTEQUAL, (struct data_info *)state->data, 0, 1);
584 exit:
585 free_string(name);
586 return ret;
589 int known_condition_true(struct expression *expr)
591 int tmp;
593 if (!expr)
594 return 0;
596 tmp = get_value(expr);
597 if (tmp && tmp != UNDEFINED)
598 return 1;
600 expr = strip_expr(expr);
601 switch(expr->type) {
602 case EXPR_PREOP:
603 if (expr->op == '!') {
604 if (known_condition_false(expr->unop))
605 return 1;
606 break;
608 break;
609 default:
610 break;
612 return 0;
615 int known_condition_false(struct expression *expr)
617 if (!expr)
618 return 0;
620 if (is_zero(expr))
621 return 1;
623 switch(expr->type) {
624 case EXPR_PREOP:
625 if (expr->op == '!') {
626 if (known_condition_true(expr->unop))
627 return 1;
628 break;
630 break;
631 default:
632 break;
634 return 0;
637 static int do_comparison_range(struct expression *expr)
639 struct symbol *sym;
640 char *name;
641 struct smatch_state *state;
642 long long value;
643 int left = 0;
644 int poss_true, poss_false;
646 value = get_value(expr->left);
647 if (value == UNDEFINED) {
648 value = get_value(expr->right);
649 if (value == UNDEFINED)
650 return 3;
651 left = 1;
653 if (left)
654 name = get_variable_from_expr(expr->left, &sym);
655 else
656 name = get_variable_from_expr(expr->right, &sym);
657 if (!name || !sym)
658 goto free;
659 state = get_state(name, SMATCH_EXTRA, sym);
660 if (!state)
661 goto free;
662 poss_true = possibly_true(expr->op, (struct data_info *)state->data, value, left);
663 poss_false = possibly_false(expr->op, (struct data_info *)state->data, value, left);
664 if (!poss_true && !poss_false)
665 return 0;
666 if (poss_true && !poss_false)
667 return 1;
668 if (!poss_true && poss_false)
669 return 2;
670 if (poss_true && poss_false)
671 return 3;
672 free:
673 free_string(name);
674 return 3;
677 int implied_condition_true(struct expression *expr)
679 struct statement *stmt;
680 int tmp;
682 if (!expr)
683 return 0;
685 tmp = get_value(expr);
686 if (tmp && tmp != UNDEFINED)
687 return 1;
689 expr = strip_expr(expr);
690 switch(expr->type) {
691 case EXPR_COMPARE:
692 if (do_comparison_range(expr) == 1)
693 return 1;
694 break;
695 case EXPR_PREOP:
696 if (expr->op == '!') {
697 if (implied_condition_false(expr->unop))
698 return 1;
699 break;
701 stmt = get_block_thing(expr);
702 if (stmt && (last_stmt_val(stmt) == 1))
703 return 1;
704 break;
705 default:
706 if (variable_non_zero(expr) == 1)
707 return 1;
708 break;
710 return 0;
713 int implied_condition_false(struct expression *expr)
715 struct statement *stmt;
716 struct expression *tmp;
718 if (!expr)
719 return 0;
721 if (is_zero(expr))
722 return 1;
724 switch(expr->type) {
725 case EXPR_COMPARE:
726 if (do_comparison_range(expr) == 2)
727 return 1;
728 case EXPR_PREOP:
729 if (expr->op == '!') {
730 if (implied_condition_true(expr->unop))
731 return 1;
732 break;
734 stmt = get_block_thing(expr);
735 if (stmt && (last_stmt_val(stmt) == 0))
736 return 1;
737 tmp = strip_expr(expr);
738 if (tmp != expr)
739 return implied_condition_false(tmp);
740 break;
741 default:
742 if (variable_non_zero(expr) == 0)
743 return 1;
744 break;
746 return 0;
749 void register_smatch_extra(int id)
751 my_id = id;
752 add_merge_hook(my_id, &merge_func);
753 add_unmatched_state_hook(my_id, &unmatched_state);
754 add_hook(&undef_expr, OP_HOOK);
755 add_hook(&match_function_def, FUNC_DEF_HOOK);
756 add_hook(&match_function_call, FUNCTION_CALL_HOOK);
757 add_hook(&match_assign, ASSIGNMENT_HOOK);
758 add_hook(&match_declarations, DECLARATION_HOOK);
759 add_hook(&match_unop, OP_HOOK);
760 add_hook(&free_data_info_allocs, END_FUNC_HOOK);
762 #ifdef KERNEL
763 /* I don't know how to test for the ATTRIB_NORET attribute. :( */
764 add_function_hook("panic", &__match_nullify_path_hook, NULL);
765 add_function_hook("do_exit", &__match_nullify_path_hook, NULL);
766 add_function_hook("complete_and_exit", &__match_nullify_path_hook, NULL);
767 add_function_hook("__module_put_and_exit", &__match_nullify_path_hook, NULL);
768 add_function_hook("do_group_exit", &__match_nullify_path_hook, NULL);
769 #endif