From 18a272e0c0ffc461707eb60690addd4fc5e608a2 Mon Sep 17 00:00:00 2001 From: Dan Carpenter Date: Mon, 4 May 2009 15:28:40 +0300 Subject: [PATCH] Rework smatch implied This is a rough commit. I hacked on it until the test cases pass. The problem was that handling compound implications didn't work. This patch adds "struct state_list *pre_merge" to sm_state. my_pools doesn't need to get copied to the merged state, it stays with the pre_merge state. With this change, we now have all the information we need to chop off pre-merged states and re-merge them to get a new state. The old code used to look at pools which were true and merge everything in those pools. The new code looks at pools which are false and chops off the false bits to find the implied states. all_pools isn't needed any more. is_merged_hook isn't needed any more because we have detailed merge info. We now consider sm_states merged even if the actual sm_state->state was the same on both sides of the merge. if (x) y = 1; else y = 1; <- (y is merged here) I added validation/sm_implied6.c which uses a compound implication. Signed-off-by: Dan Carpenter --- smatch.h | 6 +- smatch_extra.c | 68 ---------- smatch_extra.h | 2 - smatch_hooks.c | 22 ---- smatch_implied.c | 327 +++++++++++++++++++++++------------------------ smatch_ranges.c | 14 -- smatch_slist.c | 111 +++++----------- smatch_slist.h | 3 + smatch_states.c | 14 +- validation/sm_implied6.c | 41 ++++++ 10 files changed, 244 insertions(+), 364 deletions(-) create mode 100644 validation/sm_implied6.c diff --git a/smatch.h b/smatch.h index 0cdcb026..5d487efd 100644 --- a/smatch.h +++ b/smatch.h @@ -47,8 +47,9 @@ struct sm_state { struct symbol *sym; struct smatch_state *state; int line; + int merged; struct state_list_stack *my_pools; - struct state_list_stack *all_pools; + struct state_list *pre_merge; struct state_list *possible; }; @@ -76,11 +77,9 @@ typedef struct smatch_state *(merge_func_t)(const char *name, struct symbol *sym, struct smatch_state *s1, struct smatch_state *s2); -typedef int (is_merged_func_t)(struct smatch_state *state); typedef struct smatch_state *(unmatched_func_t)(struct sm_state *state); void add_merge_hook(int client_id, merge_func_t *func); void add_unmatched_state_hook(int client_id, unmatched_func_t *func); -void add_is_merged_hook(int client_id, is_merged_func_t *func); typedef void (func_hook)(const char *fn, struct expression *expr, void *data); void add_function_hook(const char *lock_for, func_hook *call_back, void *data); @@ -283,7 +282,6 @@ struct smatch_state *__client_merge_function(int owner, const char *name, struct symbol *sym, struct smatch_state *s1, struct smatch_state *s2); -int __is_merged(struct sm_state *sm); struct smatch_state *__client_unmatched_state_function(struct sm_state *sm); /* smatch_function_hooks.c */ diff --git a/smatch_extra.c b/smatch_extra.c index ce8fe6bc..dc9f3bbc 100644 --- a/smatch_extra.c +++ b/smatch_extra.c @@ -31,7 +31,6 @@ static struct smatch_state *alloc_extra_state_empty() dinfo = __alloc_data_info(0); dinfo->type = DATA_RANGE; - dinfo->merged = 0; dinfo->value_ranges = NULL; state = __alloc_smatch_state(0); state->data = dinfo; @@ -68,31 +67,6 @@ struct smatch_state *extra_undefined() return ret; } - -static int is_merged(struct smatch_state *state) -{ - return ((struct data_info *)state->data)->merged; -} - -/* This is like extra_undefined() except merged. */ -struct smatch_state *min_max_merged() -{ - struct data_info *dinfo; - static struct smatch_state *ret; - static struct symbol *prev_func; - - if (prev_func == cur_func) - return ret; - prev_func = cur_func; - - dinfo = alloc_dinfo_range(whole_range.min, whole_range.max); - dinfo->merged = 1; - ret = __alloc_smatch_state(0); - ret->name = "whole_range"; - ret->data = dinfo; - return ret; -} - struct smatch_state *alloc_extra_state(int val) { struct smatch_state *state; @@ -149,53 +123,13 @@ static struct smatch_state *merge_func(const char *name, struct symbol *sym, struct range_list *value_ranges; value_ranges = range_list_union(info1->value_ranges, info2->value_ranges); - if (is_whole_range(value_ranges)) - return min_max_merged(); tmp = alloc_extra_state_empty(); ret_info = (struct data_info *)tmp->data; - ret_info->merged = 1; ret_info->value_ranges = value_ranges; tmp->name = show_ranges(ret_info->value_ranges); return tmp; } -struct sm_state *__extra_merge(struct sm_state *one, struct state_list *slist1, - struct sm_state *two, struct state_list *slist2) -{ - struct data_info *info1; - struct data_info *info2; - - if (!one->state->data || !two->state->data) { - smatch_msg("internal error in smatch extra '%s = %s or %s'", - one->name, show_state(one->state), - show_state(two->state)); - return alloc_state(one->name, one->owner, one->sym, - extra_undefined()); - } - - info1 = (struct data_info *)one->state->data; - info2 = (struct data_info *)two->state->data; - - if (!info1->merged) - free_stack(&one->my_pools); - if (!info2->merged) - free_stack(&two->my_pools); - - if (one == two && !one->my_pools) { - add_pool(&one->my_pools, slist1); - add_pool(&one->my_pools, slist2); - } else { - if (!one->my_pools) - add_pool(&one->my_pools, slist1); - if (!two->my_pools) - add_pool(&two->my_pools, slist2); - } - - add_pool(&one->all_pools, slist1); - add_pool(&two->all_pools, slist2); - return merge_sm_states(one, two); -} - struct sm_state *__extra_and_merge(struct sm_state *sm, struct state_list_stack *stack) { @@ -219,7 +153,6 @@ struct sm_state *__extra_and_merge(struct sm_state *sm, return NULL; } ret->my_pools = stack; - ret->all_pools = clone_stack(stack); return ret; } @@ -769,7 +702,6 @@ void register_smatch_extra(int id) { my_id = id; add_merge_hook(my_id, &merge_func); - add_is_merged_hook(my_id, &is_merged); add_unmatched_state_hook(my_id, &unmatched_state); add_hook(&undef_expr, OP_HOOK); add_hook(&match_function_def, FUNC_DEF_HOOK); diff --git a/smatch_extra.h b/smatch_extra.h index c8815d67..ac1d02b7 100644 --- a/smatch_extra.h +++ b/smatch_extra.h @@ -14,7 +14,6 @@ enum data_type { DECLARE_PTR_LIST(range_list, struct data_range); struct data_info { - int merged; enum data_type type; struct range_list *value_ranges; }; @@ -51,7 +50,6 @@ struct data_info *alloc_dinfo_range(long long min, long long max); struct range_list *range_list_union(struct range_list *one, struct range_list *two); long long get_dinfo_min(struct data_info *dinfo); long long get_dinfo_max(struct data_info *dinfo); -int is_whole_range(struct range_list *ranges); long long get_single_value_from_range(struct data_info *dinfo); void function_comparison(int comparison, struct expression *expr, long long value, int left); diff --git a/smatch_hooks.c b/smatch_hooks.c index a039f9f2..91588d5f 100644 --- a/smatch_hooks.c +++ b/smatch_hooks.c @@ -18,7 +18,6 @@ ALLOCATOR(hook_container, "hook functions"); DECLARE_PTR_LIST(hook_func_list, struct hook_container); static struct hook_func_list *hook_funcs; static struct hook_func_list *merge_funcs; -static struct hook_func_list *is_merged_funcs; static struct hook_func_list *unmatched_state_funcs; void add_hook(void *func, enum hook_type type) @@ -90,14 +89,6 @@ void add_merge_hook(int client_id, merge_func_t *func) add_ptr_list(&merge_funcs, container); } -void add_is_merged_hook(int client_id, is_merged_func_t *func) -{ - struct hook_container *container = __alloc_hook_container(0); - container->data_type = client_id; - container->fn = func; - add_ptr_list(&is_merged_funcs, container); -} - void add_unmatched_state_hook(int client_id, unmatched_func_t *func) { struct hook_container *container = __alloc_hook_container(0); @@ -211,19 +202,6 @@ struct smatch_state *__client_merge_function(int owner, const char *name, return &undefined; } -int __is_merged(struct sm_state *sm) -{ - struct hook_container *tmp; - - FOR_EACH_PTR(is_merged_funcs, tmp) { - if (tmp->data_type == sm->owner) - return ((is_merged_func_t *) tmp->fn)(sm->state); - } END_FOR_EACH_PTR(tmp); - if (sm->state == &merged) - return 1; - return 0; -} - struct smatch_state *__client_unmatched_state_function(struct sm_state *sm) { struct hook_container *tmp; diff --git a/smatch_implied.c b/smatch_implied.c index d24aac9e..5847d60a 100644 --- a/smatch_implied.c +++ b/smatch_implied.c @@ -9,232 +9,220 @@ /* * Imagine we have this code: - * foo = 0; + * foo = 1; * if (bar) - * foo = 1; - * // <-- point #1 + * foo = 99; * else * frob(); - * // <-- point #2 - * if (foo == 1) // <-- point #3 - * bar->baz; // <-- point #4 + * // <-- point #1 + * if (foo == 99) // <-- point #2 + * bar->baz; // <-- point #3 * - * Currently (Oct 2008) in smatch when we merge bar states - * null and nonnull, at point #2, the state becomes undefined. - * As a result we get an error at point #3. * - * The idea behind "implied state pools" is to fix that. + * At point #3 bar is non null and can be dereferenced. * - * The implied pools get created in merge_slist(). Whatever - * is unique to one slist being merged gets put into a pool. + * It's smatch_implied.c which sets bar to non null at point #2. * - * If we set a state that removes it from all pools. - * - * When we come to an if statement where "foo" has some pools - * associated we take all the pools where "foo == 1" and keep - * all the states that are consistent across those pools. + * At point #1 merge_slist() stores the list of states from both + * the true and false paths. On the true path foo == 99 and on + * the false path foo == 1. merge_slist() sets their my_pools + * list to show the other states which were there when foo == 99. * - * The point of doing this is to turn an undefined state into - * a defined state. This hopefully gets rid of some false positives. - * What it doesn't do is find new errors that were - * missed before. + * When it comes to the if (foo == 99) the smatch implied hook + * looks for all the pools where foo was not 99. It makes a list + * of those. * - * There are quite a few implementation details I haven't figured - * out. How do you create implied state pools inside a - * complex condition? How do you determine what is implied - * from a complex condition? The initial patch is extremely rudimentary... + * Then for bar (and all the other states) it says, ok bar is a + * merged state that came from these previous states. We'll + * chop out all the states where it came from a pool where + * foo != 99 and merge it all back together. + * + * That is the implied state of bar. + * + * merge_slist() sets up ->my_pools. + * merge_sm_state() sets ->pre_merge. + * If an sm_state is not the same on both sides of a merge, it + * gets a ->my_pool set for both sides. The result is a merged + * state that has it's ->pre_merge pointers set. Merged states + * do not immediately have any my_pools set, but maybe will later + * when they themselves are merged. + * A pool is a list of all the states that were set at the time. */ #include "smatch.h" #include "smatch_slist.h" #include "smatch_extra.h" -#define EQUALS 0 -#define NOTEQUALS 1 - int debug_implied_states = 0; int option_no_implied = 0; -static int pool_in_pools(struct state_list_stack *pools, - struct state_list *pool) +static int pools_overlap(struct state_list_stack *pools1, + struct state_list_stack *pools2) { - struct state_list *tmp; + struct state_list *one; + struct state_list *two; - FOR_EACH_PTR(pools, tmp) { - if (tmp == pool) - return 1; - } END_FOR_EACH_PTR(tmp); - return 0; -} + PREPARE_PTR_LIST(pools1, one); + PREPARE_PTR_LIST(pools2, two); + for (;;) { + if (!one || !two) + return 0; -static struct state_list *clone_states_in_pool(struct state_list *pool, - struct state_list *cur_slist) -{ - struct sm_state *state; - struct sm_state *cur_state; - struct sm_state *tmp; - struct state_list *to_slist = NULL; - - FOR_EACH_PTR(pool, state) { - cur_state = get_sm_state_slist(cur_slist, state->name, - state->owner, state->sym); - if (!cur_state) - continue; - if (state == cur_state) - continue; - if (pool_in_pools(cur_state->all_pools, pool)) { - tmp = clone_state(state); - add_ptr_list(&to_slist, tmp); + if (one < two) { + NEXT_PTR_LIST(one); + } else if (one == two) { + return 1; + } else { + NEXT_PTR_LIST(two); } - } END_FOR_EACH_PTR(state); - return to_slist; + } + FINISH_PTR_LIST(two); + FINISH_PTR_LIST(one); + return 0; } -/* - * merge_implied() takes an implied state and another possibly implied state - * from another pool. It checks that the second pool is reachable from - * cur_slist then merges the two states and returns the result. - */ -static struct sm_state *merge_implied(struct sm_state *one, - struct sm_state *two, - struct state_list *pool, - struct state_list *cur_slist) +struct sm_state *remove_my_pools(struct sm_state *sm, + struct state_list_stack *pools, int *modified) { - struct sm_state *cur_state; - - cur_state = get_sm_state_slist(cur_slist, two->name, two->owner, - two->sym); - if (!cur_state) - return NULL; /* this can't actually happen */ - if (!pool_in_pools(cur_state->all_pools, pool)) + struct sm_state *ret = NULL; + struct sm_state *pre; + struct sm_state *tmp_keep; + struct state_list *keep = NULL; + + if (pools_overlap(sm->my_pools, pools)) { + DIMPLIED("removed %s = %s from %d\n", sm->name, + show_state(sm->state), sm->line); + *modified = 1; return NULL; - return merge_sm_states(one, two); -} + } -/* - * filter() is used to find what states are the same across - * a series of slists. - * It takes a **slist and a *filter. - * It removes everything from **slist that isn't in *filter. - * The reason you would want to do this is if you want to - * know what other states are true if one state is true. (smatch_implied). - */ -static void filter(struct state_list **slist, struct state_list *filter, - struct state_list *cur_slist) -{ - struct sm_state *s_one, *s_two; - struct state_list *results = NULL; - struct sm_state *tmp; + if (is_merged(sm)) { + int removed = 0; + + DIMPLIED("checking %s = %s from %d\n", sm->name, + show_state(sm->state), sm->line); + FOR_EACH_PTR(sm->pre_merge, pre) { + tmp_keep = remove_my_pools(pre, pools, &removed); + if (tmp_keep) + add_ptr_list(&keep, tmp_keep); + } END_FOR_EACH_PTR(pre); + if (!removed) { + DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state), sm->line); + return sm; + } + *modified = 1; + if (!keep) { + DIMPLIED("removed %s = %s from %d\n", sm->name, show_state(sm->state), sm->line); + return NULL; + } - PREPARE_PTR_LIST(*slist, s_one); - PREPARE_PTR_LIST(filter, s_two); - for (;;) { - if (!s_one || !s_two) - break; - if (cmp_tracker(s_one, s_two) < 0) { - DIMPLIED("removed %s\n", s_one->name); - NEXT_PTR_LIST(s_one); - } else if (cmp_tracker(s_one, s_two) == 0) { - tmp = merge_implied(s_one, s_two, filter, cur_slist); - if (tmp) - add_ptr_list(&results, tmp); + FOR_EACH_PTR(keep, tmp_keep) { + if (!ret) + ret = tmp_keep; else - DIMPLIED("removed %s\n", s_one->name); - NEXT_PTR_LIST(s_one); - NEXT_PTR_LIST(s_two); - } else { - NEXT_PTR_LIST(s_two); - } + ret = merge_sm_states(ret, tmp_keep); + } END_FOR_EACH_PTR(tmp_keep); + merge_pools(&ret->my_pools, sm->my_pools); + DIMPLIED("partial %s = %s from %d\n", sm->name, show_state(sm->state), sm->line); + return ret; } - FINISH_PTR_LIST(s_two); - FINISH_PTR_LIST(s_one); - - free_slist(slist); - *slist = results; + DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state), + sm->line); + return sm; } static struct state_list *filter_stack(struct state_list *pre_list, struct state_list_stack *stack) { - struct state_list *tmp; struct state_list *ret = NULL; - int i = 0; - - FOR_EACH_PTR(stack, tmp) { - if (!i++) { - ret = clone_states_in_pool(tmp, pre_list); - if (debug_implied_states) { - printf("The first implied pool is:\n"); - __print_slist(ret); - } - } else { - filter(&ret, tmp, pre_list); - DIMPLIED("filtered\n"); - } + struct sm_state *tmp; + struct sm_state *filtered_state; + int modified = 0; + + if (!stack) + return NULL; + + FOR_EACH_PTR(pre_list, tmp) { + filtered_state = remove_my_pools(tmp, stack, &modified); + if (filtered_state && modified) + add_ptr_list(&ret, filtered_state); } END_FOR_EACH_PTR(tmp); return ret; } -static void get_eq_neq(struct sm_state *sm_state, int comparison, int num, +static void separate_pools(struct sm_state *sm_state, int comparison, int num, int left, - struct state_list *pre_list, - struct state_list **true_states, - struct state_list **false_states) + struct state_list_stack **true_stack, + struct state_list_stack **false_stack) { struct state_list *list; struct sm_state *s; - struct state_list_stack *true_stack = NULL; - struct state_list_stack *false_stack = NULL; - - if (debug_implied_states || debug_states) { - if (left) - smatch_msg("checking implications: (%s %s %d)", - sm_state->name, show_special(comparison), num); - else - smatch_msg("checking implications: (%d %s %s)", - num, show_special(comparison), sm_state->name); - } + int istrue, isfalse; FOR_EACH_PTR(sm_state->my_pools, list) { - int istrue, isfalse; s = get_sm_state_slist(list, sm_state->name, sm_state->owner, sm_state->sym); - istrue = possibly_true(comparison, + istrue = !possibly_false(comparison, (struct data_info *)s->state->data, num, left); - isfalse = possibly_false(comparison, + isfalse = !possibly_true(comparison, (struct data_info *)s->state->data, num, left); if (debug_implied_states || debug_states) { if (istrue && isfalse) { - printf("'%s = %s' from %d could be true or " - "false.\n", s->name, - show_state(s->state), s->line); - } else if (istrue) { - printf("'%s = %s' from %d is true.\n", + printf("'%s = %s' from %d does not exist.\n", s->name, show_state(s->state), s->line); + } else if (istrue) { + printf("'%s = %s' from %d is true. %p\n", + s->name, show_state(s->state), + s->line, list); } else if (isfalse) { - printf("'%s = %s' from %d is false.\n", - s->name, show_state(s->state), - s->line); + printf("'%s = %s' from %d is false. %p\n", + s->name, show_state(s->state), + s->line, list); } else { - printf("'%s = %s' from %d does not exist.\n", - s->name, show_state(s->state), - s->line); + printf("'%s = %s' from %d could be true or " + "false.\n", s->name, + show_state(s->state), s->line); } } if (istrue) { - push_slist(&true_stack, list); + add_pool(true_stack, list); } if (isfalse) { - push_slist(&false_stack, list); + add_pool(false_stack, list); } } END_FOR_EACH_PTR(list); + FOR_EACH_PTR(sm_state->pre_merge, s) { + separate_pools(s, comparison, num, left, true_stack, false_stack); + } END_FOR_EACH_PTR(s); +} + +static void get_eq_neq(struct sm_state *sm_state, int comparison, int num, + int left, + struct state_list *pre_list, + struct state_list **true_states, + struct state_list **false_states) +{ + struct state_list_stack *true_stack = NULL; + struct state_list_stack *false_stack = NULL; + + if (debug_implied_states || debug_states) { + if (left) + smatch_msg("checking implications: (%s %s %d)", + sm_state->name, show_special(comparison), num); + else + smatch_msg("checking implications: (%d %s %s)", + num, show_special(comparison), sm_state->name); + } + + separate_pools(sm_state, comparison, num, left, &true_stack, &false_stack); + DIMPLIED("filtering true stack.\n"); - *true_states = filter_stack(pre_list, true_stack); + *true_states = filter_stack(pre_list, false_stack); DIMPLIED("filtering false stack.\n"); - *false_states = filter_stack(pre_list, false_stack); + *false_states = filter_stack(pre_list, true_stack); free_stack(&true_stack); free_stack(&false_stack); if (debug_implied_states || debug_states) { @@ -279,8 +267,8 @@ static void handle_comparison(struct expression *expr, state = get_sm_state(name, SMATCH_EXTRA, sym); if (!state) goto free; - if (!state->my_pools) { - DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name); + if (!is_merged(state)) { + DIMPLIED("%d '%s' is not merged.\n", get_lineno(), state->name); goto free; } get_eq_neq(state, expr->op, value, left, __get_cur_slist(), implied_true, implied_false); @@ -315,7 +303,7 @@ static void get_tf_states(struct expression *expr, state = get_sm_state(name, SMATCH_EXTRA, sym); if (!state) goto free; - if (!state->my_pools) { + if (!is_merged(state)) { DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name); goto free; } @@ -369,6 +357,7 @@ struct state_list *__implied_case_slist(struct expression *switch_expr, char *name = NULL; struct symbol *sym; struct sm_state *sm; + struct sm_state *true_sm; struct sm_state *false_sm; struct state_list *true_states = NULL; struct state_list *false_states = NULL; @@ -386,15 +375,15 @@ struct state_list *__implied_case_slist(struct expression *switch_expr, goto free; if (sm) { get_eq_neq(sm, SPECIAL_EQUAL, val, 1, *raw_slist, &true_states, &false_states); - } else { - true_states = clone_slist(*raw_slist); } - set_state_slist(&true_states, name, SMATCH_EXTRA, sym, alloc_extra_state(val)); + + true_sm = get_sm_state_slist(true_states, name, SMATCH_EXTRA, sym); + if (!true_sm) + set_state_slist(&true_states, name, SMATCH_EXTRA, sym, alloc_extra_state(val)); false_sm = get_sm_state_slist(false_states, name, SMATCH_EXTRA, sym); - if (false_sm) - overwrite_sm_state(raw_slist, false_sm); - else - set_state_slist(raw_slist, name, SMATCH_EXTRA, sym, add_filter(sm?sm->state:NULL, val)); + if (!false_sm) + set_state_slist(&false_states, name, SMATCH_EXTRA, sym, add_filter(sm?sm->state:NULL, val)); + overwrite_slist(false_states, raw_slist); overwrite_slist(true_states, &ret); free_slist(&true_states); free_slist(&false_states); diff --git a/smatch_ranges.c b/smatch_ranges.c index 6d02b391..0c82c7c3 100644 --- a/smatch_ranges.c +++ b/smatch_ranges.c @@ -110,7 +110,6 @@ struct data_info *alloc_dinfo_range(long long min, long long max) ret = __alloc_data_info(0); ret->type = DATA_RANGE; - ret->merged = 0; ret->value_ranges = NULL; add_range(&ret->value_ranges, min, max); return ret; @@ -235,19 +234,6 @@ long long get_dinfo_max(struct data_info *dinfo) return drange->max; } -int is_whole_range(struct range_list *ranges) -{ - struct data_range *drange; - - if (!ranges) - return 0; - - drange = first_ptr_list((struct ptr_list *)ranges); - if (drange->min == whole_range.min && drange->max == whole_range.max) - return 1; - return 0; -} - /* * if it can be only one value return that, else return UNDEFINED */ diff --git a/smatch_slist.c b/smatch_slist.c index 78acce38..d7475d15 100644 --- a/smatch_slist.c +++ b/smatch_slist.c @@ -14,7 +14,6 @@ #include "smatch_extra.h" #undef CHECKORDER -#undef CHECKMYPOOLS ALLOCATOR(smatch_state, "smatch state"); ALLOCATOR(sm_state, "sm state"); @@ -162,8 +161,9 @@ struct sm_state *alloc_state(const char *name, int owner, sm_state->sym = sym; sm_state->state = state; sm_state->line = get_lineno(); + sm_state->merged = 0; sm_state->my_pools = NULL; - sm_state->all_pools = NULL; + sm_state->pre_merge = NULL; sm_state->possible = NULL; add_ptr_list(&sm_state->possible, sm_state); return sm_state; @@ -172,8 +172,8 @@ struct sm_state *alloc_state(const char *name, int owner, static void free_sm_state(struct sm_state *sm) { free_slist(&sm->possible); + free_slist(&sm->pre_merge); free_stack(&sm->my_pools); - free_stack(&sm->all_pools); /* * fixme. Free the actual state. * Right now we leave it until the end of the function @@ -216,18 +216,21 @@ void free_every_single_sm_state(void) struct sm_state *clone_state(struct sm_state *s) { struct sm_state *ret; - struct sm_state *poss; ret = alloc_state_no_name(s->name, s->owner, s->sym, s->state); ret->line = s->line; + ret->merged = s->merged; ret->my_pools = clone_stack(s->my_pools); - ret->all_pools = clone_stack(s->all_pools); - FOR_EACH_PTR(s->possible, poss) { - add_sm_state_slist(&ret->possible, poss); - } END_FOR_EACH_PTR(poss); + ret->possible = clone_slist(s->possible); + ret->pre_merge = clone_slist(s->pre_merge); return ret; } +int is_merged(struct sm_state *sm) +{ + return sm->merged; +} + int slist_has_state(struct state_list *slist, struct smatch_state *state) { struct sm_state *tmp; @@ -260,50 +263,28 @@ static void check_order(struct state_list *slist) printf("======\n"); #endif } -#ifdef CHECKMYPOOLS -static void check_my_pools(struct sm_state *sm) -{ - struct sm_state *poss; - struct state_list *slist; - - if (sm->state != &merged) - return; - - FOR_EACH_PTR(sm->possible, poss) { - if (poss->state == &merged) - continue; - FOR_EACH_PTR(sm->my_pools, slist) { - if (get_state_slist(slist, sm->name, sm->owner, sm->sym) - == poss->state) - goto found; - } END_FOR_EACH_PTR(slist); - printf("%d pool not found for '%s' possible state \"%s\".\n", - get_lineno(), sm->name, show_state(poss->state)); - return; -found: - continue; - } END_FOR_EACH_PTR(poss); -} -#endif -static void sanity_check_pools(struct state_list *slist) +struct state_list *clone_slist(struct state_list *from_slist) { -#ifdef CHECKMYPOOLS - struct sm_state *tmp; + struct sm_state *state; + struct state_list *to_slist = NULL; - FOR_EACH_PTR(slist, tmp) { - check_my_pools(tmp); - } END_FOR_EACH_PTR(tmp); -#endif + FOR_EACH_PTR(from_slist, state) { + add_ptr_list(&to_slist, state); + } END_FOR_EACH_PTR(state); + check_order(to_slist); + return to_slist; } -struct state_list *clone_slist(struct state_list *from_slist) +struct state_list *clone_slist_and_states(struct state_list *from_slist) { struct sm_state *state; + struct sm_state *tmp; struct state_list *to_slist = NULL; FOR_EACH_PTR(from_slist, state) { - add_ptr_list(&to_slist, state); + tmp = clone_state(state); + add_ptr_list(&to_slist, tmp); } END_FOR_EACH_PTR(state); check_order(to_slist); return to_slist; @@ -359,19 +340,12 @@ void add_pool(struct state_list_stack **pools, struct state_list *new) add_ptr_list(pools, new); } -static void copy_pools(struct sm_state *to, struct sm_state *sm) +void merge_pools(struct state_list_stack **to, struct state_list_stack *from) { struct state_list *tmp; - if (!sm) - return; - - FOR_EACH_PTR(sm->my_pools, tmp) { - add_pool(&to->my_pools, tmp); - } END_FOR_EACH_PTR(tmp); - - FOR_EACH_PTR(sm->all_pools, tmp) { - add_pool(&to->all_pools, tmp); + FOR_EACH_PTR(from, tmp) { + add_pool(to, tmp); } END_FOR_EACH_PTR(tmp); } @@ -387,10 +361,11 @@ struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two) result = alloc_state_no_name(one->name, one->owner, one->sym, s); if (two && one->line == two->line) result->line = one->line; + result->merged = 1; + add_ptr_list(&result->pre_merge, one); + add_ptr_list(&result->pre_merge, two); add_possible(result, one); add_possible(result, two); - copy_pools(result, one); - copy_pools(result, two); if (debug_states) { struct sm_state *tmp; @@ -633,8 +608,6 @@ void merge_slist(struct state_list **to, struct state_list *slist) check_order(*to); check_order(slist); - sanity_check_pools(*to); - sanity_check_pools(slist); /* merging a null and nonnull path gives you only the nonnull path */ if (!slist) { @@ -659,32 +632,11 @@ void merge_slist(struct state_list **to, struct state_list *slist) smatch_msg("error: Internal smatch error."); NEXT_PTR_LIST(to_state); } else if (cmp_tracker(to_state, state) == 0) { - if (state->owner == SMATCH_EXTRA) { - tmp = __extra_merge(to_state, implied_to, - state, implied_from); - add_ptr_list(&results, tmp); - NEXT_PTR_LIST(to_state); - NEXT_PTR_LIST(state); - continue; - } - if (!__is_merged(to_state)) - free_stack(&to_state->my_pools); - if (!__is_merged(state)) - free_stack(&state->my_pools); - - if (to_state == state && !state->my_pools) { - add_pool(&state->my_pools, implied_to); + if (to_state != state) { + add_pool(&to_state->my_pools, implied_to); add_pool(&state->my_pools, implied_from); - } else { - if (!to_state->my_pools) - add_pool(&to_state->my_pools, implied_to); - if (!state->my_pools) - add_pool(&state->my_pools, implied_from); } - add_pool(&to_state->all_pools, implied_to); - add_pool(&state->all_pools, implied_from); - tmp = merge_sm_states(to_state, state); add_ptr_list(&results, tmp); NEXT_PTR_LIST(to_state); @@ -778,7 +730,6 @@ static struct sm_state *find_intersection(struct sm_state *one, add_possible(ret, tmp_state); } END_FOR_EACH_PTR(tmp1); ret->my_pools = stack; - ret->all_pools = clone_stack(stack); return ret; } diff --git a/smatch_slist.h b/smatch_slist.h index 5d2ef3d8..0a0d2d05 100644 --- a/smatch_slist.h +++ b/smatch_slist.h @@ -19,7 +19,9 @@ struct sm_state *alloc_state(const char *name, int owner, void free_every_single_sm_state(void); struct sm_state *clone_state(struct sm_state *s); +int is_merged(struct sm_state *sm); struct state_list *clone_slist(struct state_list *from_slist); +struct state_list *clone_slist_and_states(struct state_list *from_slist); struct state_list_stack *clone_stack(struct state_list_stack *from_stack); int slist_has_state(struct state_list *slist, struct smatch_state *state); @@ -29,6 +31,7 @@ struct smatch_state *merge_states(const char *name, int owner, struct smatch_state *state2); void add_pool(struct state_list_stack **pools, struct state_list *new); +void merge_pools(struct state_list_stack **to, struct state_list_stack *from); struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two); struct smatch_state *get_state_slist(struct state_list *slist, const char *name, int owner, struct symbol *sym); diff --git a/smatch_states.c b/smatch_states.c index 00d8d963..8a057101 100644 --- a/smatch_states.c +++ b/smatch_states.c @@ -581,12 +581,15 @@ void __save_switch_states() void __merge_switches(struct expression *switch_expr, struct expression *case_expr) { struct state_list *slist; + struct state_list *cloned; struct state_list *implied_slist; slist = pop_slist(&switch_stack); implied_slist = __implied_case_slist(switch_expr, case_expr, &slist); - merge_slist(&cur_slist, implied_slist); + cloned = clone_slist_and_states(implied_slist); + merge_slist(&cur_slist, cloned); free_slist(&implied_slist); + free_slist(&cloned); push_slist(&switch_stack, slist); } @@ -633,17 +636,18 @@ static struct named_slist *alloc_named_slist(const char *name, void __save_gotos(const char *name) { struct state_list **slist; + struct state_list *clone; slist = get_slist_from_named_stack(goto_stack, name); if (slist) { - merge_slist(slist, cur_slist); + clone = clone_slist_and_states(cur_slist); + merge_slist(slist, clone); return; } else { - struct state_list *slist; struct named_slist *named_slist; - slist = clone_slist(cur_slist); - named_slist = alloc_named_slist(name, slist); + clone = clone_slist(cur_slist); + named_slist = alloc_named_slist(name, clone); add_ptr_list(&goto_stack, named_slist); } } diff --git a/validation/sm_implied6.c b/validation/sm_implied6.c new file mode 100644 index 00000000..fca95a12 --- /dev/null +++ b/validation/sm_implied6.c @@ -0,0 +1,41 @@ +struct foo { + int a; +}; + +struct foo *a; +struct foo *b; +struct foo *c; +struct foo *d; +int x, y, z; + +void func (void) +{ + a = 0; + b = 0; + c = 0; + d = 0; + + if (x) + a = returns_nonnull(); + else + b = returns_nonnull(); + if (y) + a = returns_nonnull(); + else + c = returns_nonnull(); + __smatch_extra_values(); + if (x || y) { + a->a = 1; + b->a = 2; + }else { + c->a = 3; + } +} +/* + * check-name: Smatch implied #6 + * check-command: smatch sm_implied6.c + * + * check-output-start +sm_implied6.c +29 func(18) error: dereferencing undefined: 'b' + * check-output-end + */ -- 2.11.4.GIT