smatch_constraints.c

   1 /*
   2  * sparse/smatch_constraints.c
   3  *
   4  * Copyright (C) 2010 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * smatch_constraints.c is for tracking how variables are related
  12  *
  13  * if (a == b) {
  14  * if (a > b) {
  15  * if (a != b) {
  16  *
  17  * This is stored in a field in the smatch_extra dinfo.
  18  *
  19  * Normally the way that variables become related is through a
  20  * condition and you say:  add_constraint_expr(left, '<', right);
  21  * The other way it can happen is if you have an assignment:
  22  * set_equiv(left, right);
  23  *
  24  * One two variables "a" and "b" are related if then if we find
  25  * that "a" is greater than 0 we need to update "b".
  26  *
  27  * When a variable gets modified all the old relationships are
  28  * deleted.  remove_contraints(expr);
  29  *
  30  * Also we need an is_true_constraint(left, '<', right) and
  31  * is_false_constraint (left, '<', right).  This is used by
  32  * smatch_implied.
  33  *
  34  */
  35
  36 #include "smatch.h"
  37 #include "smatch_slist.h"
  38 #include "smatch_extra.h"
  39
  40 ALLOCATOR(relation, "related variables");
  41
  42 static struct relation *alloc_relation(int op, const char *name, struct symbol *sym)
  43 {
  44         struct relation *tmp;
  45
  46         tmp = __alloc_relation(0);
  47         tmp->op = op;
  48         tmp->name = alloc_string(name);
  49         tmp->sym = sym;
  50         return tmp;
  51 }
  52
  53 struct related_list *clone_related_list(struct related_list *related)
  54 {
  55         struct relation *rel;
  56         struct related_list *to_list = NULL;
  57
  58         FOR_EACH_PTR(related, rel) {
  59                 add_ptr_list(&to_list, rel);
  60         } END_FOR_EACH_PTR(rel);
  61
  62         return to_list;
  63 }
  64
  65 struct relation *get_common_relationship(struct data_info *dinfo, int op,
  66                                         const char *name, struct symbol *sym)
  67 {
  68         struct relation *tmp;
  69
  70         // FIXME...
  71         // Find the common x < y and x <= y
  72         FOR_EACH_PTR(dinfo->related, tmp) {
  73                 if (tmp->op < op || tmp->sym < sym || strcmp(tmp->name, name) < 0)
  74                         continue;
  75                 if (tmp->op == op && tmp->sym == sym && !strcmp(tmp->name, name))
  76                         return tmp;
  77                 return NULL;
  78         } END_FOR_EACH_PTR(tmp);
  79         return NULL;
  80 }
  81
  82 void add_related(struct smatch_state *state, int op, const char *name, struct symbol *sym)
  83 {
  84         struct data_info *dinfo;
  85         struct relation *tmp;
  86         struct relation *new;
  87
  88         dinfo = get_dinfo(state);
  89         FOR_EACH_PTR(dinfo->related, tmp) {
  90                 if (tmp->op < op || tmp->sym < sym || strcmp(tmp->name, name) < 0)
  91                         continue;
  92                 if (tmp->op == op && tmp->sym == sym && !strcmp(tmp->name, name))
  93                         return;
  94                 new = alloc_relation(op, name, sym);
  95                 INSERT_CURRENT(new, tmp);
  96                 return;
  97         } END_FOR_EACH_PTR(tmp);
  98         new = alloc_relation(op, name, sym);
  99         add_ptr_list(&dinfo->related, new);
 100 }
 101
 102 void del_related(struct smatch_state *state, int op, const char *name, struct symbol *sym)
 103 {
 104         struct data_info *dinfo;
 105         struct relation *tmp;
 106
 107         dinfo = get_dinfo(state);
 108         FOR_EACH_PTR(dinfo->related, tmp) {
 109                 if (tmp->sym < sym || strcmp(tmp->name, name) < 0)
 110                         continue;
 111                 if (tmp->sym == sym && !strcmp(tmp->name, name)) {
 112                         DELETE_CURRENT_PTR(tmp);
 113                         continue;
 114                 }
 115                 return;
 116         } END_FOR_EACH_PTR(tmp);
 117 }
 118
 119 void add_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 120 {
 121         add_related(state, SPECIAL_EQUAL, name, sym);
 122 }
 123
 124 static void del_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 125 {
 126         del_related(state, SPECIAL_EQUAL, name, sym);
 127 }
 128
 129 void remove_from_equiv(const char *name, struct symbol *sym)
 130 {
 131         struct sm_state *orig_sm;
 132         struct relation *rel;
 133         struct smatch_state *state;
 134         struct related_list *to_update;
 135
 136         // FIXME equiv => related
 137         orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
 138         if (!orig_sm || !get_dinfo(orig_sm->state)->related)
 139                 return;
 140
 141         state = clone_extra_state(orig_sm->state);
 142         del_equiv(state, name, sym);
 143         to_update = get_dinfo(state)->related;
 144         if (ptr_list_size((struct ptr_list *)get_dinfo(state)->related) == 1)
 145                 get_dinfo(state)->related = NULL;
 146
 147         FOR_EACH_PTR(to_update, rel) {
 148                 struct sm_state *new_sm;
 149
 150                 new_sm = clone_sm(orig_sm);
 151                 new_sm->name = rel->name;
 152                 new_sm->sym = rel->sym;
 153                 new_sm->state = state;
 154                 __set_sm(new_sm);
 155         } END_FOR_EACH_PTR(rel);
 156 }
 157
 158 void remove_from_equiv_expr(struct expression *expr)
 159 {
 160         char *name;
 161         struct symbol *sym;
 162
 163         name = get_variable_from_expr(expr, &sym);
 164         if (!name || !sym)
 165                 goto free;
 166         remove_from_equiv(name, sym);
 167 free:
 168         free_string(name);
 169 }
 170
 171 void add_constrain_expr(struct expression *left, int op, struct expression *right)
 172 {
 173
 174 }
 175
 176 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
 177 {
 178         struct relation *rel;
 179         struct smatch_state *extra_state;
 180
 181         extra_state = get_state_expr(SMATCH_EXTRA, expr);
 182
 183         if (!extra_state)
 184                 return;
 185
 186         FOR_EACH_PTR(get_dinfo(extra_state)->related, rel) {
 187                 if (rel->op != SPECIAL_EQUAL)
 188                         continue;
 189                 set_state(id, rel->name, rel->sym, state);
 190         } END_FOR_EACH_PTR(rel);
 191 }