smatch_estate.c

   1 /*
   2  * smatch/smatch_dinfo.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_dinfo.c has helper functions for handling data_info structs
  12  *
  13  */
  14
  15 #include <stdlib.h>
  16 #ifndef __USE_ISOC99
  17 #define __USE_ISOC99
  18 #endif
  19 #include <limits.h>
  20 #include "parse.h"
  21 #include "smatch.h"
  22 #include "smatch_slist.h"
  23 #include "smatch_extra.h"
  24
  25 struct smatch_state *merge_estates(struct smatch_state *s1, struct smatch_state *s2)
  26 {
  27         struct smatch_state *tmp;
  28         struct range_list *value_ranges;
  29         struct related_list *rlist;
  30
  31         if (estates_equiv(s1, s2))
  32                 return s1;
  33
  34         value_ranges = rl_union(estate_rl(s1), estate_rl(s2));
  35         tmp = alloc_estate_rl(value_ranges);
  36         rlist = get_shared_relations(estate_related(s1), estate_related(s2));
  37         set_related(tmp, rlist);
  38         if (estate_has_hard_max(s1) && estate_has_hard_max(s2))
  39                 estate_set_hard_max(tmp);
  40
  41         return tmp;
  42 }
  43
  44 struct data_info *get_dinfo(struct smatch_state *state)
  45 {
  46         if (!state)
  47                 return NULL;
  48         return (struct data_info *)state->data;
  49 }
  50
  51 struct range_list *estate_rl(struct smatch_state *state)
  52 {
  53         if (!state)
  54                 return NULL;
  55         return get_dinfo(state)->value_ranges;
  56 }
  57
  58 struct related_list *estate_related(struct smatch_state *state)
  59 {
  60         if (!state)
  61                 return NULL;
  62         return get_dinfo(state)->related;
  63 }
  64
  65 int estate_has_hard_max(struct smatch_state *state)
  66 {
  67         if (!state)
  68                 return 0;
  69         return get_dinfo(state)->hard_max;
  70 }
  71
  72 void estate_set_hard_max(struct smatch_state *state)
  73 {
  74          get_dinfo(state)->hard_max = 1;
  75 }
  76
  77 void estate_clear_hard_max(struct smatch_state *state)
  78 {
  79          get_dinfo(state)->hard_max = 0;
  80 }
  81
  82 int estate_get_hard_max(struct smatch_state *state, sval_t *sval)
  83 {
  84         if (!state || !get_dinfo(state)->hard_max || !estate_rl(state))
  85                 return 0;
  86         *sval = rl_max(estate_rl(state));
  87         return 1;
  88 }
  89
  90 sval_t estate_min(struct smatch_state *state)
  91 {
  92         return rl_min(estate_rl(state));
  93 }
  94
  95 sval_t estate_max(struct smatch_state *state)
  96 {
  97         return rl_max(estate_rl(state));
  98 }
  99
 100 struct symbol *estate_type(struct smatch_state *state)
 101 {
 102         return rl_max(estate_rl(state)).type;
 103 }
 104
 105 static int rlists_equiv(struct related_list *one, struct related_list *two)
 106 {
 107         struct relation *one_rel;
 108         struct relation *two_rel;
 109
 110         PREPARE_PTR_LIST(one, one_rel);
 111         PREPARE_PTR_LIST(two, two_rel);
 112         for (;;) {
 113                 if (!one_rel && !two_rel)
 114                         return 1;
 115                 if (!one_rel || !two_rel)
 116                         return 0;
 117                 if (one_rel->sym != two_rel->sym)
 118                         return 0;
 119                 if (strcmp(one_rel->name, two_rel->name))
 120                         return 0;
 121                 NEXT_PTR_LIST(one_rel);
 122                 NEXT_PTR_LIST(two_rel);
 123         }
 124         FINISH_PTR_LIST(two_rel);
 125         FINISH_PTR_LIST(one_rel);
 126
 127         return 1;
 128 }
 129
 130 int estates_equiv(struct smatch_state *one, struct smatch_state *two)
 131 {
 132         if (one == two)
 133                 return 1;
 134         if (!rlists_equiv(estate_related(one), estate_related(two)))
 135                 return 0;
 136         if (strcmp(one->name, two->name) == 0)
 137                 return 1;
 138         return 0;
 139 }
 140
 141 int estate_is_whole(struct smatch_state *state)
 142 {
 143         return is_whole_rl(estate_rl(state));
 144 }
 145
 146 int estate_get_single_value(struct smatch_state *state, sval_t *sval)
 147 {
 148         sval_t min, max;
 149
 150         min = rl_min(estate_rl(state));
 151         max = rl_max(estate_rl(state));
 152         if (sval_cmp(min, max) != 0)
 153                 return 0;
 154         *sval = min;
 155         return 1;
 156 }
 157
 158 static struct data_info *alloc_dinfo(void)
 159 {
 160         struct data_info *ret;
 161
 162         ret = __alloc_data_info(0);
 163         ret->related = NULL;
 164         ret->value_ranges = NULL;
 165         ret->hard_max = 0;
 166         return ret;
 167 }
 168
 169 static struct data_info *alloc_dinfo_range(sval_t min, sval_t max)
 170 {
 171         struct data_info *ret;
 172
 173         ret = alloc_dinfo();
 174         add_range(&ret->value_ranges, min, max);
 175         return ret;
 176 }
 177
 178 static struct data_info *alloc_dinfo_range_list(struct range_list *rl)
 179 {
 180         struct data_info *ret;
 181
 182         ret = alloc_dinfo();
 183         ret->value_ranges = rl;
 184         return ret;
 185 }
 186
 187 static struct data_info *clone_dinfo(struct data_info *dinfo)
 188 {
 189         struct data_info *ret;
 190
 191         ret = alloc_dinfo();
 192         ret->related = clone_related_list(dinfo->related);
 193         ret->value_ranges = clone_rl(dinfo->value_ranges);
 194         ret->hard_max = dinfo->hard_max;
 195         return ret;
 196 }
 197
 198 struct smatch_state *clone_estate(struct smatch_state *state)
 199 {
 200         struct smatch_state *ret;
 201
 202         ret = __alloc_smatch_state(0);
 203         ret->name = state->name;
 204         ret->data = clone_dinfo(get_dinfo(state));
 205         return ret;
 206 }
 207
 208 struct smatch_state *alloc_estate_empty(void)
 209 {
 210         struct smatch_state *state;
 211         struct data_info *dinfo;
 212
 213         dinfo = alloc_dinfo();
 214         state = __alloc_smatch_state(0);
 215         state->data = dinfo;
 216         state->name = "";
 217         return state;
 218 }
 219
 220 struct smatch_state *alloc_estate_whole(struct symbol *type)
 221 {
 222         return alloc_estate_rl(alloc_whole_rl(type));
 223 }
 224
 225 struct smatch_state *extra_empty(void)
 226 {
 227         struct smatch_state *ret;
 228
 229         ret = __alloc_smatch_state(0);
 230         ret->name = "empty";
 231         ret->data = alloc_dinfo();
 232         return ret;
 233 }
 234
 235 struct smatch_state *alloc_estate_sval(sval_t sval)
 236 {
 237         struct smatch_state *state;
 238
 239         state = __alloc_smatch_state(0);
 240         state->data = alloc_dinfo_range(sval, sval);
 241         state->name = show_rl(get_dinfo(state)->value_ranges);
 242         estate_set_hard_max(state);
 243         return state;
 244 }
 245
 246 struct smatch_state *alloc_estate_range(sval_t min, sval_t max)
 247 {
 248         struct smatch_state *state;
 249
 250         state = __alloc_smatch_state(0);
 251         state->data = alloc_dinfo_range(min, max);
 252         state->name = show_rl(get_dinfo(state)->value_ranges);
 253         return state;
 254 }
 255
 256 struct smatch_state *alloc_estate_rl(struct range_list *rl)
 257 {
 258         struct smatch_state *state;
 259
 260         if (!rl)
 261                 return extra_empty();
 262
 263         state = __alloc_smatch_state(0);
 264         state->data = alloc_dinfo_range_list(rl);
 265         state->name = show_rl(rl);
 266         return state;
 267 }
 268
 269 struct smatch_state *get_implied_estate(struct expression *expr)
 270 {
 271         struct smatch_state *state;
 272         struct range_list *rl;
 273
 274         state = get_state_expr(SMATCH_EXTRA, expr);
 275         if (state)
 276                 return state;
 277         if (!get_implied_rl(expr, &rl))
 278                 rl = alloc_whole_rl(get_type(expr));
 279         return alloc_estate_rl(rl);
 280 }
 281
 282 struct smatch_state *estate_filter_range(struct smatch_state *orig,
 283                                  sval_t filter_min, sval_t filter_max)
 284 {
 285         struct range_list *rl;
 286
 287         if (!orig)
 288                 orig = alloc_estate_whole(filter_min.type);
 289
 290         rl = remove_range(estate_rl(orig), filter_min, filter_max);
 291         return alloc_estate_rl(rl);
 292 }
 293
 294 struct smatch_state *estate_filter_sval(struct smatch_state *orig, sval_t sval)
 295 {
 296         return estate_filter_range(orig, sval, sval);
 297 }
 298
 299