From: Dan Carpenter Date: Thu, 22 May 2014 09:42:50 +0000 (+0300) Subject: slist: introduce merge_fake_stree() X-Git-Tag: 1.60~244 X-Git-Url: https://repo.or.cz/w/smatch.git/commitdiff_plain/c1a7786a5ac71ec84b8c61f82d79a56f30fd9bf4 slist: introduce merge_fake_stree() This process of having fake_strees is very subtle and tricky but we also need it. How a fake stree works is that we store the current stree, then we put a layer on in front of the current stree to record any states which are changed. Then we look at the code. This gives us a list of states which are affect by this change. The problem that this patch addresses is that we want to merge two fake strees together, but there is an unmatched state. Instead of defaulting to &undefined, we should default to the original state. You might ask why we don't just use all the states and not just the set ones? I did try that, and it didn't work... Signed-off-by: Dan Carpenter --- diff --git a/smatch_function_hooks.c b/smatch_function_hooks.c index 33c247eb..b697fc92 100644 --- a/smatch_function_hooks.c +++ b/smatch_function_hooks.c @@ -269,7 +269,7 @@ static int assign_ranged_funcs(const char *fn, struct expression *expr, set_extra_mod(var_name, sym, estate); tmp_stree = __pop_fake_cur_stree(); - merge_stree(&final_states, tmp_stree); + merge_fake_stree(&final_states, tmp_stree); free_stree(&tmp_stree); handled = 1; } END_FOR_EACH_PTR(tmp); @@ -313,7 +313,7 @@ static int call_implies_callbacks(int comparison, struct expression *expr, sval_ (tmp->u.ranged)(fn, expr, NULL, tmp->info); } END_FOR_EACH_PTR(tmp); tmp_stree = __pop_fake_cur_stree(); - merge_stree(&true_states, tmp_stree); + merge_fake_stree(&true_states, tmp_stree); free_stree(&tmp_stree); /* set false states */ @@ -326,7 +326,7 @@ static int call_implies_callbacks(int comparison, struct expression *expr, sval_ (tmp->u.ranged)(fn, expr, NULL, tmp->info); } END_FOR_EACH_PTR(tmp); tmp_stree = __pop_fake_cur_stree(); - merge_stree(&false_states, tmp_stree); + merge_fake_stree(&false_states, tmp_stree); free_stree(&tmp_stree); FOR_EACH_SM(true_states, sm) { @@ -464,7 +464,7 @@ static int db_assign_return_states_callback(void *unused, int argc, char **argv, if (prev_return_id != -1 && return_id != prev_return_id) { stree = __pop_fake_cur_stree(); - merge_stree(&db_info.stree, stree); + merge_fake_stree(&db_info.stree, stree); free_stree(&stree); __push_fake_cur_stree(); } @@ -501,7 +501,7 @@ static int db_return_states_assign(struct expression *expr) sql_select_return_states("return_id, return, type, parameter, key, value", right, db_assign_return_states_callback); stree = __pop_fake_cur_stree(); - merge_stree(&db_info.stree, stree); + merge_fake_stree(&db_info.stree, stree); free_stree(&stree); FOR_EACH_SM(db_info.stree, sm) { @@ -594,7 +594,7 @@ static int db_return_states_callback(void *unused, int argc, char **argv, char * if (prev_return_id != -1 && return_id != prev_return_id) { stree = __pop_fake_cur_stree(); - merge_stree(&db_info.stree, stree); + merge_fake_stree(&db_info.stree, stree); free_stree(&stree); __push_fake_cur_stree(); __unnullify_path(); @@ -630,7 +630,7 @@ static void db_return_states(struct expression *expr) sql_select_return_states("return_id, return, type, parameter, key, value", expr, db_return_states_callback); stree = __pop_fake_cur_stree(); - merge_stree(&db_info.stree, stree); + merge_fake_stree(&db_info.stree, stree); free_stree(&stree); FOR_EACH_SM(db_info.stree, sm) { diff --git a/smatch_slist.c b/smatch_slist.c index a0400696..e2c1ad16 100644 --- a/smatch_slist.c +++ b/smatch_slist.c @@ -694,6 +694,73 @@ void merge_stree_no_pools(struct stree **to, struct stree *stree) { __merge_stree(to, stree, 0); } + +/* + * This is unfortunately a bit subtle... The problem is that if a + * state is set on one fake stree but not the other then we should + * look up the the original state and use that as the unset state. + * Fortunately, after you pop your fake stree then the cur_slist should + * reflect the original state. + */ +void merge_fake_stree(struct stree **to, struct stree *stree) +{ + struct stree *one = *to; + struct stree *two = stree; + struct sm_state *sm; + struct state_list *add_to_one = NULL; + struct state_list *add_to_two = NULL; + AvlIter one_iter; + AvlIter two_iter; + + if (!stree) + return; + if (*to == stree) + return; + if (!*to) { + *to = clone_stree(stree); + return; + } + + avl_iter_begin(&one_iter, one, FORWARD); + avl_iter_begin(&two_iter, two, FORWARD); + + for (;;) { + if (!one_iter.sm && !two_iter.sm) + break; + if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) { + sm = get_sm_state(one_iter.sm->owner, one_iter.sm->name, + one_iter.sm->sym); + if (sm) + add_ptr_list(&add_to_two, sm); + avl_iter_next(&one_iter); + } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) { + avl_iter_next(&one_iter); + avl_iter_next(&two_iter); + } else { + sm = get_sm_state(two_iter.sm->owner, two_iter.sm->name, + two_iter.sm->sym); + if (sm) + add_ptr_list(&add_to_one, sm); + avl_iter_next(&two_iter); + } + } + + FOR_EACH_PTR(add_to_one, sm) { + avl_insert(&one, sm); + } END_FOR_EACH_PTR(sm); + + FOR_EACH_PTR(add_to_two, sm) { + avl_insert(&two, sm); + } END_FOR_EACH_PTR(sm); + + free_slist(&add_to_one); + free_slist(&add_to_two); + + __merge_stree(&one, two, 1); + + *to = one; +} + /* * filter_slist() removes any sm states "slist" holds in common with "filter" */ diff --git a/smatch_slist.h b/smatch_slist.h index 24945250..d619e400 100644 --- a/smatch_slist.h +++ b/smatch_slist.h @@ -69,6 +69,7 @@ int out_of_memory(void); int low_on_memory(void); void merge_stree(struct stree **to, struct stree *stree); void merge_stree_no_pools(struct stree **to, struct stree *stree); +void merge_fake_stree(struct stree **to, struct stree *stree); void filter_stree(struct stree **stree, struct stree *filter); void and_stree_stack(struct stree_stack **stree_stack);