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 /*
  52  * This function gets all the states which are implied by a non zero value.
  53  * So for example for the code:
  54  * if (c) {
  55  * We would want to know what was implied by c is non zero.
  56  */
  57
  58 static struct state_list *get_non_zero_filtered(struct sm_state *sm_state)
  59 {
  60         struct state_list *list;
  61         struct smatch_state *s;
  62         struct state_list *ret = NULL;
  63
  64         FOR_EACH_PTR(sm_state->pools, list) {
  65                 s = get_state_slist(list, sm_state->name, sm_state->owner,
  66                                     sm_state->sym);
  67                 if (s == &undefined) {
  68                         del_slist(&ret);
  69                         return NULL;
  70                 }
  71                 if (s->data && *(int *)s->data != 0) {
  72                         if (!ret)
  73                                 ret = clone_slist(list);
  74                         else
  75                                 filter(&ret, list);
  76                 }
  77         } END_FOR_EACH_PTR(list);
  78         return ret;
  79 }
  80
  81 /*
  82  * What are the implications if (foo == num) ...
  83  */
  84
  85 static struct state_list *get_equals_filtered(struct sm_state *sm_state, int num)
  86 {
  87         struct state_list *list;
  88         struct smatch_state *s;
  89         struct state_list *ret = NULL;
  90
  91         FOR_EACH_PTR(sm_state->pools, list) {
  92                 s = get_state_slist(list, sm_state->name, sm_state->owner,
  93                                     sm_state->sym);
  94                 if (s == &undefined) {
  95                         del_slist(&ret);
  96                         return NULL;
  97                 }
  98                 if (s->data && *(int *)s->data == num) {
  99                         if (!ret)
 100                                 ret = clone_slist(list);
 101                         else
 102                                 filter(&ret, list);
 103                 }
 104         } END_FOR_EACH_PTR(list);
 105         return ret;
 106 }
 107
 108
 109 /*
 110  * This condition hook is very connected to smatch_extra.c.
 111  * It's registered there.
 112  */
 113
 114 void __implied_states_hook(struct expression *expr)
 115 {
 116         struct symbol *sym;
 117         char *name;
 118         struct sm_state *state;
 119         struct state_list *implied_true;
 120         struct state_list *implied_false;
 121
 122         name = get_variable_from_expr(expr, &sym);
 123         if (!name || !sym)
 124                 return;
 125         state = __get_sm_state(name, SMATCH_EXTRA, sym);
 126         if (!state)
 127                 return;
 128         if (!state->pools)
 129                 return;
 130         implied_true = get_non_zero_filtered(state);
 131         implied_false = get_equals_filtered(state, 0);
 132         if (debug_states) {
 133                 printf("Setting the following implied states for the true path.\n");
 134                 __print_slist(implied_true);
 135         }
 136
 137         /* FIXME.  We lose the ->pools by doing this. */
 138         FOR_EACH_PTR(implied_true, state) {
 139                 set_true_false_states(state->name, state->owner, state->sym,
 140                                 state->state, NULL);
 141         } END_FOR_EACH_PTR(state);
 142
 143         if (debug_states) {
 144                 printf("Setting the following implied states for the false path.\n");
 145                 __print_slist(implied_false);
 146         }
 147
 148         FOR_EACH_PTR(implied_false, state) {
 149                 set_true_false_states(state->name, state->owner, state->sym,
 150                                 NULL, state->state);
 151         } END_FOR_EACH_PTR(state);
 152
 153         free_string(name);
 154 }