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 #include "smatch_extra.h"
  51
  52 #define EQUALS 0
  53 #define NOTEQUALS 1
  54
  55 int debug_implied_states = 0;
  56 int option_no_implied = 0;
  57
  58 static int pool_in_pools(struct state_list_stack *pools,
  59                         struct state_list *pool)
  60 {
  61         struct state_list *tmp;
  62
  63         FOR_EACH_PTR(pools, tmp) {
  64                 if (tmp == pool)
  65                         return 1;
  66         } END_FOR_EACH_PTR(tmp);
  67         return 0;
  68 }
  69
  70 static struct state_list *clone_states_in_pool(struct sm_state *implication_state,
  71                                         struct state_list *pool,
  72                                         struct state_list *cur_slist)
  73 {
  74         struct sm_state *state;
  75         struct sm_state *cur_state;
  76         struct sm_state *tmp;
  77         struct state_list *to_slist = NULL;
  78
  79         FOR_EACH_PTR(pool, state) {
  80                 if (!cmp_tracker(state, implication_state))
  81                         continue;
  82                 cur_state = get_sm_state_slist(cur_slist, state->name,
  83                                         state->owner, state->sym);
  84                 if (!cur_state)
  85                         continue;
  86                 if (state == cur_state)
  87                         continue;
  88                 if (pool_in_pools(cur_state->all_pools, pool)) {
  89                         tmp = clone_state(state);
  90                         add_ptr_list(&to_slist, tmp);
  91                 }
  92         } END_FOR_EACH_PTR(state);
  93         return to_slist;
  94 }
  95
  96 /*
  97  * merge_implied() takes an implied state and another possibly implied state
  98  * from another pool.  It checks that the second pool is reachable from
  99  * cur_slist then merges the two states and returns the result.
 100  */
 101 static struct sm_state *merge_implied(struct sm_state *one,
 102                                       struct sm_state *two,
 103                                       struct state_list *pool,
 104                                       struct state_list *cur_slist)
 105 {
 106         struct sm_state *cur_state;
 107
 108         cur_state = get_sm_state_slist(cur_slist, two->name, two->owner,
 109                                 two->sym);
 110         if (!cur_state)
 111                 return NULL;  /* this can't actually happen */
 112         if (!pool_in_pools(cur_state->all_pools, pool))
 113                 return NULL;
 114         return merge_sm_states(one, two);
 115 }
 116
 117 /*
 118  * filter() is used to find what states are the same across
 119  * a series of slists.
 120  * It takes a **slist and a *filter.
 121  * It removes everything from **slist that isn't in *filter.
 122  * The reason you would want to do this is if you want to
 123  * know what other states are true if one state is true.  (smatch_implied).
 124  */
 125 static void filter(struct state_list **slist, struct state_list *filter,
 126                 struct state_list *cur_slist)
 127 {
 128         struct sm_state *s_one, *s_two;
 129         struct state_list *results = NULL;
 130         struct sm_state *tmp;
 131
 132         PREPARE_PTR_LIST(*slist, s_one);
 133         PREPARE_PTR_LIST(filter, s_two);
 134         for (;;) {
 135                 if (!s_one || !s_two)
 136                         break;
 137                 if (cmp_tracker(s_one, s_two) < 0) {
 138                         DIMPLIED("removed %s\n", s_one->name);
 139                         NEXT_PTR_LIST(s_one);
 140                 } else if (cmp_tracker(s_one, s_two) == 0) {
 141                         tmp = merge_implied(s_one, s_two, filter, cur_slist);
 142                         if (tmp)
 143                                 add_ptr_list(&results, tmp);
 144                         else
 145                                 DIMPLIED("removed %s\n", s_one->name);
 146                         NEXT_PTR_LIST(s_one);
 147                         NEXT_PTR_LIST(s_two);
 148                 } else {
 149                         NEXT_PTR_LIST(s_two);
 150                 }
 151         }
 152         FINISH_PTR_LIST(s_two);
 153         FINISH_PTR_LIST(s_one);
 154
 155         free_slist(slist);
 156         *slist = results;
 157 }
 158
 159 static struct state_list *filter_stack(struct sm_state *implication_state,
 160                                 struct state_list_stack *stack)
 161 {
 162         struct state_list *tmp;
 163         struct state_list *ret = NULL;
 164         int i = 0;
 165
 166         FOR_EACH_PTR(stack, tmp) {
 167                 if (!i++) {
 168                         ret = clone_states_in_pool(implication_state, tmp, __get_cur_slist());
 169                         if (debug_implied_states) {
 170                                 printf("The first implied pool is:\n");
 171                                 __print_slist(ret);
 172                         }
 173                 } else {
 174                         filter(&ret, tmp, __get_cur_slist());
 175                         DIMPLIED("filtered\n");
 176                 }
 177         } END_FOR_EACH_PTR(tmp);
 178         return ret;
 179 }
 180
 181 static void get_eq_neq(struct sm_state *sm_state, int comparison, int num,
 182                        int left, struct state_list **true_states,
 183                        struct state_list **false_states)
 184 {
 185         struct state_list *list;
 186         struct sm_state *s;
 187         struct state_list_stack *true_stack = NULL;
 188         struct state_list_stack *false_stack = NULL;
 189
 190         if (debug_implied_states || debug_states) {
 191                 if (left)
 192                         smatch_msg("checking implications: (%s %s %d)",
 193                                 sm_state->name, show_special(comparison), num);
 194                 else
 195                         smatch_msg("checking implications: (%d %s %s)",
 196                                 num, show_special(comparison), sm_state->name);
 197         }
 198
 199         FOR_EACH_PTR(sm_state->my_pools, list) {
 200                 int istrue, isfalse;
 201                 s = get_sm_state_slist(list, sm_state->name, sm_state->owner,
 202                                     sm_state->sym);
 203                 istrue = possibly_true(comparison,
 204                                        (struct data_info *)s->state->data, num,
 205                                        left);
 206                 isfalse = possibly_false(comparison,
 207                                          (struct data_info *)s->state->data,
 208                                          num, left);
 209                 if (debug_implied_states || debug_states) {
 210                         if (istrue && isfalse) {
 211                                 printf("'%s = %s' from %d could be true or "
 212                                          "false.\n", s->name,
 213                                          show_state(s->state), s->line);
 214                         } else if (istrue) {
 215                                 printf("'%s = %s' from %d is true.\n",
 216                                          s->name, show_state(s->state),
 217                                          s->line);
 218                         } else if (isfalse) {
 219                                 printf("'%s = %s' from %d is false.\n",
 220                                          s->name, show_state(s->state),
 221                                          s->line);
 222                         } else {
 223                                 printf("'%s = %s' from %d does not exist.\n",
 224                                          s->name, show_state(s->state),
 225                                          s->line);
 226                         }
 227                 }
 228                 if (istrue) {
 229                         push_slist(&true_stack, list);
 230                 }
 231                 if (isfalse) {
 232                         push_slist(&false_stack, list);
 233                 }
 234         } END_FOR_EACH_PTR(list);
 235         DIMPLIED("filtering true stack.\n");
 236         *true_states = filter_stack(sm_state, true_stack);
 237         DIMPLIED("filtering false stack.\n");
 238         *false_states = filter_stack(sm_state, false_stack);
 239         free_stack(&true_stack);
 240         free_stack(&false_stack);
 241         if (debug_implied_states || debug_states) {
 242                 printf("These are the implied states for the true path:\n");
 243                 __print_slist(*true_states);
 244                 printf("These are the implied states for the false path:\n");
 245                 __print_slist(*false_states);
 246         }
 247 }
 248
 249 static void handle_comparison(struct expression *expr,
 250                               struct state_list **implied_true,
 251                               struct state_list **implied_false)
 252 {
 253         struct symbol *sym;
 254         char *name;
 255         struct sm_state *state;
 256         int value;
 257         int left = 0;
 258
 259         value = get_value(expr->left);
 260         if (value == UNDEFINED) {
 261                 value = get_value(expr->right);
 262                 if (value == UNDEFINED)
 263                         return;
 264                 left = 1;
 265         }
 266         if (left)
 267                 name = get_variable_from_expr(expr->left, &sym);
 268         else
 269                 name = get_variable_from_expr(expr->right, &sym);
 270         if (!name || !sym) {
 271                 free_string(name);
 272                 return;
 273         }
 274         state = get_sm_state(name, SMATCH_EXTRA, sym);
 275         free_string(name);
 276         if (!state)
 277                 return;
 278         if (!state->my_pools) {
 279                 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name);
 280                 return;
 281         }
 282         get_eq_neq(state, expr->op, value, left, implied_true, implied_false);
 283 }
 284
 285 static void get_tf_states(struct expression *expr,
 286                           struct state_list **implied_true,
 287                           struct state_list **implied_false)
 288 {
 289         struct symbol *sym;
 290         char *name;
 291         struct sm_state *state;
 292
 293         if (expr->type == EXPR_COMPARE) {
 294                 handle_comparison(expr, implied_true, implied_false);
 295                 return;
 296         }
 297         if (expr->type == EXPR_ASSIGNMENT) {
 298                 /* most of the time ->my_pools will be empty here because we
 299                    just set the state, but if have assigned a conditional
 300                    function there are implications. */
 301                 expr = expr->left;
 302         }
 303
 304         name = get_variable_from_expr(expr, &sym);
 305         if (!name || !sym) {
 306                 free_string(name);
 307                 return;
 308         }
 309         state = get_sm_state(name, SMATCH_EXTRA, sym);
 310         free_string(name);
 311         if (!state)
 312                 return;
 313         if (!state->my_pools) {
 314                 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name);
 315                 return;
 316         }
 317         get_eq_neq(state, SPECIAL_NOTEQUAL, 0, 1, implied_true, implied_false);
 318 }
 319
 320 static void implied_states_hook(struct expression *expr)
 321 {
 322         struct sm_state *state;
 323         struct state_list *implied_true = NULL;
 324         struct state_list *implied_false = NULL;
 325
 326         if (option_no_implied)
 327                 return;
 328
 329         get_tf_states(expr, &implied_true, &implied_false);
 330
 331         FOR_EACH_PTR(implied_true, state) {
 332                 __set_true_false_sm(state, NULL);
 333         } END_FOR_EACH_PTR(state);
 334         free_slist(&implied_true);
 335
 336         FOR_EACH_PTR(implied_false, state) {
 337                 __set_true_false_sm(NULL, state);
 338         } END_FOR_EACH_PTR(state);
 339         free_slist(&implied_false);
 340 }
 341
 342 void get_implications(char *name, struct symbol *sym, int comparison, int num,
 343                       struct state_list **true_states,
 344                       struct state_list **false_states)
 345 {
 346         struct sm_state *sm;
 347
 348         sm = get_sm_state(name, SMATCH_EXTRA, sym);
 349         if (!sm)
 350                 return;
 351         if (slist_has_state(sm->possible, &undefined))
 352                 return;
 353         get_eq_neq(sm, comparison, num, 1, true_states, false_states);
 354 }
 355
 356 void __extra_match_condition(struct expression *expr);
 357 void register_implications(int id)
 358 {
 359         add_hook(&implied_states_hook, CONDITION_HOOK);
 360         add_hook(&__extra_match_condition, CONDITION_HOOK);
 361 }