slist: introduce merge_fake_stree()
authorDan Carpenter <dan.carpenter@oracle.com>
Thu, 22 May 2014 09:42:50 +0000 (22 12:42 +0300)
committerDan Carpenter <dan.carpenter@oracle.com>
Thu, 22 May 2014 09:42:50 +0000 (22 12:42 +0300)
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 <dan.carpenter@oracle.com>
smatch_function_hooks.c
smatch_slist.c
smatch_slist.h

index 33c247e..b697fc9 100644 (file)
@@ -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) {
index a040069..e2c1ad1 100644 (file)
@@ -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"
  */
index 2494525..d619e40 100644 (file)
@@ -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);