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 static struct state_list *filter_stack(struct state_list_stack *stack)
  58 {
  59         struct state_list *tmp;
  60         struct state_list *ret = NULL;
  61         int i = 0;
  62
  63         FOR_EACH_PTR(stack, tmp) {
  64                 if (!i++) {
  65                         ret = clone_states_in_pool(tmp, __get_cur_slist());
  66                         if (debug_implied_states) {
  67                                 printf("The first implied pool is:\n");
  68                                 __print_slist(ret);
  69                         }
  70                 } else {
  71                         filter(&ret, tmp, __get_cur_slist());
  72                         DIMPLIED("filtered\n");
  73                 }
  74         } END_FOR_EACH_PTR(tmp);
  75         return ret;
  76 }
  77
  78 static void get_eq_neq(struct sm_state *sm_state, int comparison, int num,
  79                        int left, struct state_list **true_states,
  80                        struct state_list **false_states)
  81 {
  82         struct state_list *list;
  83         struct smatch_state *s;
  84         struct state_list_stack *true_stack = NULL;
  85         struct state_list_stack *false_stack = NULL;
  86         int tf;
  87
  88         FOR_EACH_PTR(sm_state->my_pools, list) {
  89                 s = get_state_slist(list, sm_state->name, sm_state->owner,
  90                                     sm_state->sym);
  91                 if (s == &undefined || !s->data) {
  92                         free_stack(&true_stack);
  93                         free_stack(&false_stack);
  94                         DIMPLIED("%d '%s' is undefined\n", get_lineno(),
  95                                  sm_state->name);
  96                         return;
  97                 }
  98                 if (left)
  99                         tf = true_comparison(*(int *)s->data,  comparison, num);
 100                 else
 101                         tf = true_comparison(num,  comparison, *(int *)s->data);
 102                 if (tf) {
 103                         push_slist(&true_stack, list);
 104                 } else {
 105                         push_slist(&false_stack, list);
 106                 }
 107         } END_FOR_EACH_PTR(list);
 108         *true_states = filter_stack(true_stack);
 109         *false_states = filter_stack(false_stack);
 110         free_stack(&true_stack);
 111         free_stack(&false_stack);
 112 }
 113
 114 static void handle_comparison(struct expression *expr,
 115                               struct state_list **implied_true,
 116                               struct state_list **implied_false)
 117 {
 118         struct symbol *sym;
 119         char *name;
 120         struct sm_state *state;
 121         int value;
 122         int left = 0;
 123
 124         value = get_value(expr->left);
 125         if (value == UNDEFINED) {
 126                 value = get_value(expr->right);
 127                 if (value == UNDEFINED)
 128                         return;
 129                 left = 1;
 130         }
 131         if (left)
 132                 name = get_variable_from_expr(expr->left, &sym);
 133         else
 134                 name = get_variable_from_expr(expr->right, &sym);
 135         if (!name || !sym) {
 136                 free_string(name);
 137                 return;
 138         }
 139         state = get_sm_state(name, SMATCH_EXTRA, sym);
 140         free_string(name);
 141         if (!state)
 142                 return;
 143         if (!state->my_pools) {
 144                 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name);
 145                 return;
 146         }
 147         get_eq_neq(state, expr->op, value, left, implied_true, implied_false);
 148 }
 149
 150 static void get_tf_states(struct expression *expr,
 151                           struct state_list **implied_true,
 152                           struct state_list **implied_false)
 153 {
 154         struct symbol *sym;
 155         char *name;
 156         struct sm_state *state;
 157
 158         if (expr->type == EXPR_COMPARE) {
 159                 handle_comparison(expr, implied_true, implied_false);
 160                 return;
 161         }
 162
 163         name = get_variable_from_expr(expr, &sym);
 164         if (!name || !sym) {
 165                 free_string(name);
 166                 return;
 167         }
 168         state = get_sm_state(name, SMATCH_EXTRA, sym);
 169         free_string(name);
 170         if (!state)
 171                 return;
 172         if (!state->my_pools) {
 173                 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name);
 174                 return;
 175         }
 176         get_eq_neq(state, SPECIAL_NOTEQUAL, 0, 1, implied_true, implied_false);
 177 }
 178
 179 static void implied_states_hook(struct expression *expr)
 180 {
 181         struct sm_state *state;
 182         struct state_list *implied_true = NULL;
 183         struct state_list *implied_false = NULL;
 184
 185         if (option_no_implied)
 186                 return;
 187
 188         get_tf_states(expr, &implied_true, &implied_false);
 189
 190         FOR_EACH_PTR(implied_true, state) {
 191                 __set_true_false_sm(state, NULL);
 192         } END_FOR_EACH_PTR(state);
 193         free_slist(&implied_true);
 194
 195         FOR_EACH_PTR(implied_false, state) {
 196                 __set_true_false_sm(NULL, state);
 197         } END_FOR_EACH_PTR(state);
 198         free_slist(&implied_false);
 199 }
 200
 201 void register_implications(int id)
 202 {
 203         add_hook(&implied_states_hook, CONDITION_HOOK);
 204 }