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 int debug_implied_states = 0;
  55 int option_no_implied = 0;
  56
  57 /*
  58  * What are the implications if (foo == num) ...
  59  */
  60
  61 static struct state_list_stack *get_eq_neq(struct sm_state *sm_state,
  62                                         int eq_neq, int num)
  63 {
  64         struct state_list *list;
  65         struct smatch_state *s;
  66         struct state_list_stack *ret = NULL;
  67
  68         FOR_EACH_PTR(sm_state->my_pools, list) {
  69                 s = get_state_slist(list, sm_state->name, sm_state->owner,
  70                                     sm_state->sym);
  71                 if (s == &undefined) {
  72                         free_stack(&ret);
  73                         DIMPLIED("%d '%s' is undefined\n", get_lineno(),
  74                                  sm_state->name);
  75                         return NULL;
  76                 }
  77                 if (s->data && ((eq_neq == EQUALS && *(int *)s->data == num) ||
  78                                 (eq_neq == NOTEQUALS && *(int *)s->data != num))) {
  79                         DIMPLIED("added pool where %s is %s from line %d.\n",
  80                                  sm_state->name, show_state(s),
  81                                  sm_state->line);
  82                         push_slist(&ret, list);
  83                 }
  84         } END_FOR_EACH_PTR(list);
  85         return ret;
  86 }
  87
  88 static struct state_list *filter_stack(struct state_list_stack *stack)
  89 {
  90         struct state_list *tmp;
  91         struct state_list *ret = NULL;
  92         int i = 0;
  93
  94         FOR_EACH_PTR(stack, tmp) {
  95                 if (!i++) {
  96                         ret = clone_states_in_pool(tmp, __get_cur_slist());
  97                         if (debug_implied_states) {
  98                                 printf("The first implied pool is:\n");
  99                                 __print_slist(ret);
 100                         }
 101                 } else {
 102                         filter(&ret, tmp, __get_cur_slist());
 103                         DIMPLIED("filtered\n");
 104                 }
 105         } END_FOR_EACH_PTR(tmp);
 106         return ret;
 107 }
 108
 109 void __implied_states_hook(struct expression *expr)
 110 {
 111         struct symbol *sym;
 112         char *name;
 113         struct sm_state *state;
 114         struct state_list_stack *true_pools;
 115         struct state_list_stack *false_pools;
 116         struct state_list *implied_true;
 117         struct state_list *implied_false;
 118
 119         if (option_no_implied)
 120                 return;
 121
 122         name = get_variable_from_expr(expr, &sym);
 123         if (!name || !sym) {
 124                 free_string(name);
 125                 return;
 126         }
 127         state = get_sm_state(name, SMATCH_EXTRA, sym);
 128         free_string(name);
 129         if (!state)
 130                 return;
 131         if (!state->my_pools) {
 132                 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name);
 133                 return;
 134         }
 135
 136         if (debug_implied_states) {
 137                 printf("%s has the following possible states:\n", state->name);
 138                 __print_slist(state->possible);
 139         }
 140
 141         DIMPLIED("Gettin the implied states for (%s != 0)\n", state->name);
 142         true_pools = get_eq_neq(state, NOTEQUALS, 0);
 143         DIMPLIED("There are %s implied pools for (%s != 0).\n", (true_pools?"some":"no"), state->name);
 144         implied_true = filter_stack(true_pools);
 145         if (implied_true && (debug_states || debug_implied_states)) {
 146                 printf("Setting the following implied states for (%s != 0).\n",
 147                        state->name);
 148                 __print_slist(implied_true);
 149         }
 150         DIMPLIED("Gettin the implied states for (%s == 0)\n", state->name);
 151         false_pools = get_eq_neq(state, EQUALS, 0);
 152         DIMPLIED("There are %s implied pools for (%s == 0).\n", (true_pools?"some":"no"), state->name);
 153         implied_false = filter_stack(false_pools);
 154         if (implied_false && (debug_states || debug_implied_states)) {
 155                 printf("Setting the following implied states for (%s == 0).\n",
 156                        state->name);
 157                 __print_slist(implied_false);
 158         }
 159
 160         FOR_EACH_PTR(implied_true, state) {
 161                 __set_true_false_sm(state, NULL);
 162         } END_FOR_EACH_PTR(state);
 163         free_stack(&true_pools);
 164         free_slist(&implied_true);
 165
 166         FOR_EACH_PTR(implied_false, state) {
 167                 __set_true_false_sm(NULL, state);
 168         } END_FOR_EACH_PTR(state);
 169         free_stack(&false_pools);
 170         free_slist(&implied_false);
 171 }
 172
 173 void register_implications(int id)
 174 {
 175         add_hook(&__implied_states_hook, CONDITION_HOOK);
 176 }