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->type = DATA_RANGE;
 165         ret->value_ranges = NULL;
 166         ret->hard_max = 0;
 167         return ret;
 168 }
 169
 170 static struct data_info *alloc_dinfo_range(sval_t min, sval_t max)
 171 {
 172         struct data_info *ret;
 173
 174         ret = alloc_dinfo();
 175         add_range(&ret->value_ranges, min, max);
 176         return ret;
 177 }
 178
 179 static struct data_info *alloc_dinfo_range_list(struct range_list *rl)
 180 {
 181         struct data_info *ret;
 182
 183         ret = alloc_dinfo();
 184         ret->value_ranges = rl;
 185         return ret;
 186 }
 187
 188 static struct data_info *clone_dinfo(struct data_info *dinfo)
 189 {
 190         struct data_info *ret;
 191
 192         ret = alloc_dinfo();
 193         ret->related = clone_related_list(dinfo->related);
 194         ret->value_ranges = clone_rl(dinfo->value_ranges);
 195         ret->hard_max = dinfo->hard_max;
 196         return ret;
 197 }
 198
 199 struct smatch_state *clone_estate(struct smatch_state *state)
 200 {
 201         struct smatch_state *ret;
 202
 203         ret = __alloc_smatch_state(0);
 204         ret->name = state->name;
 205         ret->data = clone_dinfo(get_dinfo(state));
 206         return ret;
 207 }
 208
 209 struct smatch_state *alloc_estate_empty(void)
 210 {
 211         struct smatch_state *state;
 212         struct data_info *dinfo;
 213
 214         dinfo = alloc_dinfo();
 215         state = __alloc_smatch_state(0);
 216         state->data = dinfo;
 217         state->name = "";
 218         return state;
 219 }
 220
 221 struct smatch_state *alloc_estate_whole(struct symbol *type)
 222 {
 223         return alloc_estate_rl(alloc_whole_rl(type));
 224 }
 225
 226 struct smatch_state *extra_empty(void)
 227 {
 228         struct smatch_state *ret;
 229
 230         ret = __alloc_smatch_state(0);
 231         ret->name = "empty";
 232         ret->data = alloc_dinfo();
 233         return ret;
 234 }
 235
 236 struct smatch_state *alloc_estate_sval(sval_t sval)
 237 {
 238         struct smatch_state *state;
 239
 240         state = __alloc_smatch_state(0);
 241         state->data = alloc_dinfo_range(sval, sval);
 242         state->name = show_rl(get_dinfo(state)->value_ranges);
 243         estate_set_hard_max(state);
 244         return state;
 245 }
 246
 247 struct smatch_state *alloc_estate_range(sval_t min, sval_t max)
 248 {
 249         struct smatch_state *state;
 250
 251         state = __alloc_smatch_state(0);
 252         state->data = alloc_dinfo_range(min, max);
 253         state->name = show_rl(get_dinfo(state)->value_ranges);
 254         return state;
 255 }
 256
 257 struct smatch_state *alloc_estate_rl(struct range_list *rl)
 258 {
 259         struct smatch_state *state;
 260
 261         if (!rl)
 262                 return extra_empty();
 263
 264         state = __alloc_smatch_state(0);
 265         state->data = alloc_dinfo_range_list(rl);
 266         state->name = show_rl(rl);
 267         return state;
 268 }
 269
 270 struct smatch_state *get_implied_estate(struct expression *expr)
 271 {
 272         struct smatch_state *state;
 273         struct range_list *rl;
 274
 275         state = get_state_expr(SMATCH_EXTRA, expr);
 276         if (state)
 277                 return state;
 278         if (!get_implied_rl(expr, &rl))
 279                 rl = alloc_whole_rl(get_type(expr));
 280         return alloc_estate_rl(rl);
 281 }
 282
 283 struct smatch_state *estate_filter_range(struct smatch_state *orig,
 284                                  sval_t filter_min, sval_t filter_max)
 285 {
 286         struct range_list *rl;
 287
 288         if (!orig)
 289                 orig = alloc_estate_whole(filter_min.type);
 290
 291         rl = remove_range(estate_rl(orig), filter_min, filter_max);
 292         return alloc_estate_rl(rl);
 293 }
 294
 295 struct smatch_state *estate_filter_sval(struct smatch_state *orig, sval_t sval)
 296 {
 297         return estate_filter_range(orig, sval, sval);
 298 }
 299
 300