smatch_implied.c

   1 /*
   2  * sparse/smatch_implied.c
   3  *
   4  * Copyright (C) 2008 Dan Carpenter.
   5  *
   6  *  Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * Imagine we have this code:
  12  * foo = 0;
  13  * if (bar)
  14  *         foo = 1;
  15  *                   //  <-- point #1
  16  * else
  17  *         frob();
  18  *                   //  <-- point #2
  19  * if (foo == 1)     //  <-- point #3
  20  *         bar->baz; //  <-- point #4
  21  *
  22  * Currently (Oct 2008) in smatch when we merge bar states
  23  * null and nonnull, at point #2, the state becomes undefined.
  24  * As a result we get an error at point #3.
  25  *
  26  * The idea behind "implied state pools" is to fix that.
  27  *
  28  * The implied pools get created in merge_slist().  Whatever
  29  * is unique to one slist being merged gets put into a pool.
  30  *
  31  * If we set a state that removes it from all pools.
  32  *
  33  * When we come to an if statement where "foo" has some pools
  34  * associated we take all the pools where "foo == 1" and keep
  35  * all the states that are consistent across those pools.
  36  *
  37  * The point of doing this is to turn an undefined state into
  38  * a defined state.  This hopefully gets rid of some false positives.
  39  * What it doesn't do is find new errors that were
  40  * missed before.
  41  *
  42  * There are quite a few implementation details I haven't figured
  43  * out.  How do you create implied state pools inside a
  44  * complex condition?  How do you determine what is implied
  45  * from a complex condition?  The initial patch is extremely rudimentary...
  46  */
  47
  48 #include "smatch.h"
  49 #include "smatch_slist.h"
  50
  51 #define EQUALS 0
  52 #define NOTEQUALS 1
  53
  54 /*
  55  * What are the implications if (foo == num) ...
  56  */
  57
  58 static struct state_list_stack *get_eq_neq(struct sm_state *sm_state,
  59                                         int eq_neq, int num)
  60 {
  61         struct state_list *list;
  62         struct smatch_state *s;
  63         struct state_list_stack *ret = NULL;
  64
  65         FOR_EACH_PTR(sm_state->pools, list) {
  66                 s = get_state_slist(list, sm_state->name, sm_state->owner,
  67                                     sm_state->sym);
  68                 if (s == &undefined) {
  69                         __free_ptr_list((struct ptr_list **)&ret);
  70                         return NULL;
  71                 }
  72                 if (s->data && ((eq_neq == EQUALS && *(int *)s->data == num) ||
  73                                 (eq_neq == NOTEQUALS && *(int *)s->data != num))) {
  74                         push_slist(&ret, list);
  75                 }
  76         } END_FOR_EACH_PTR(list);
  77         return ret;
  78 }
  79
  80 static struct state_list *filter_stack(struct state_list_stack *stack)
  81 {
  82         struct state_list *tmp;
  83         struct state_list *ret = NULL;
  84         int i = 0;
  85
  86         FOR_EACH_PTR(stack, tmp) {
  87                 if (!i++)
  88                         ret = clone_states_in_pool(tmp, __get_cur_slist());
  89                 else
  90                         filter(&ret, tmp, __get_cur_slist());
  91         } END_FOR_EACH_PTR(tmp);
  92         return ret;
  93 }
  94
  95 /*
  96  * Make sure that the implied true and implied false states are different.
  97  * No need to set the states if they're just going to be the same on both
  98  * sides.
  99  */
 100 void harmonize_states(struct state_list **imp_true, struct state_list **imp_false)
 101 {
 102         struct sm_state *sm_true;
 103         struct sm_state *sm_false;
 104
 105         PREPARE_PTR_LIST(*imp_true, sm_true);
 106         PREPARE_PTR_LIST(*imp_false, sm_false);
 107         for (;;) {
 108                 if (!sm_true && !sm_false)
 109                         break;
 110                 if (cmp_tracker(sm_true, sm_false) < 0) {
 111                         NEXT_PTR_LIST(sm_true);
 112                 } else if (cmp_tracker(sm_true, sm_false) == 0) {
 113                         if (sm_true->state == sm_false->state) {
 114                                 DELETE_CURRENT_PTR(sm_true);
 115                                 DELETE_CURRENT_PTR(sm_false);
 116                         }
 117                         NEXT_PTR_LIST(sm_true);
 118                         NEXT_PTR_LIST(sm_false);
 119                 } else {
 120                         NEXT_PTR_LIST(sm_false);
 121                 }
 122         }
 123         FINISH_PTR_LIST(sm_false);
 124         FINISH_PTR_LIST(sm_true);
 125 }
 126
 127 void __implied_states_hook(struct expression *expr)
 128 {
 129         struct symbol *sym;
 130         char *name;
 131         struct sm_state *state;
 132         struct state_list_stack *true_pools;
 133         struct state_list_stack *false_pools;
 134         struct state_list *implied_true;
 135         struct state_list *implied_false;
 136
 137         name = get_variable_from_expr(expr, &sym);
 138         if (!name || !sym)
 139                 return;
 140         state = get_sm_state(name, SMATCH_EXTRA, sym);
 141         if (!state)
 142                 return;
 143         if (!state->pools)
 144                 return;
 145
 146         true_pools = get_eq_neq(state, NOTEQUALS, 0);
 147         false_pools = get_eq_neq(state, EQUALS, 0);
 148         implied_true = filter_stack(true_pools);
 149         implied_false = filter_stack(false_pools);
 150         harmonize_states(&implied_true, &implied_false);
 151         if (debug_states) {
 152                 printf("Setting the following implied states for the true path.\n");
 153                 __print_slist(implied_true);
 154         }
 155
 156         /* FIXME.  We lose the ->pools by doing this. */
 157         FOR_EACH_PTR(implied_true, state) {
 158                 set_true_false_states(state->name, state->owner, state->sym,
 159                                 state->state, NULL);
 160         } END_FOR_EACH_PTR(state);
 161
 162         if (debug_states) {
 163                 printf("Setting the following implied states for the false path.\n");
 164                 __print_slist(implied_false);
 165         }
 166
 167         FOR_EACH_PTR(implied_false, state) {
 168                 set_true_false_states(state->name, state->owner, state->sym,
 169                                 NULL, state->state);
 170         } END_FOR_EACH_PTR(state);
 171
 172         free_string(name);
 173 }
 174
 175 void register_implications(int id)
 176 {
 177         add_hook(&__implied_states_hook, CONDITION_HOOK);
 178 }