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         estate_set_fuzzy_max(tmp, sval_max(estate_get_fuzzy_max(s1), estate_get_fuzzy_max(s2)));
  42
  43         return tmp;
  44 }
  45
  46 struct data_info *get_dinfo(struct smatch_state *state)
  47 {
  48         if (!state)
  49                 return NULL;
  50         return (struct data_info *)state->data;
  51 }
  52
  53 struct range_list *estate_rl(struct smatch_state *state)
  54 {
  55         if (!state)
  56                 return NULL;
  57         return get_dinfo(state)->value_ranges;
  58 }
  59
  60 struct related_list *estate_related(struct smatch_state *state)
  61 {
  62         if (!state)
  63                 return NULL;
  64         return get_dinfo(state)->related;
  65 }
  66
  67 sval_t estate_get_fuzzy_max(struct smatch_state *state)
  68 {
  69         sval_t empty = {};
  70
  71         if (!state || !get_dinfo(state))
  72                 return empty;
  73         return get_dinfo(state)->fuzzy_max;
  74 }
  75
  76 int estate_has_fuzzy_max(struct smatch_state *state)
  77 {
  78         if (estate_get_fuzzy_max(state).type)
  79                 return 1;
  80         return 0;
  81 }
  82
  83 void estate_set_fuzzy_max(struct smatch_state *state, sval_t fuzzy_max)
  84 {
  85         if (!rl_has_sval(estate_rl(state), fuzzy_max))
  86                 return;
  87         get_dinfo(state)->fuzzy_max = fuzzy_max;
  88 }
  89
  90 void estate_copy_fuzzy_max(struct smatch_state *new, struct smatch_state *old)
  91 {
  92         if (!estate_has_fuzzy_max(old))
  93                 return;
  94         estate_set_fuzzy_max(new, estate_get_fuzzy_max(old));
  95 }
  96
  97 void estate_clear_fuzzy_max(struct smatch_state *state)
  98 {
  99         sval_t empty = {};
 100
 101         get_dinfo(state)->fuzzy_max = empty;
 102 }
 103
 104 int estate_has_hard_max(struct smatch_state *state)
 105 {
 106         if (!state)
 107                 return 0;
 108         return get_dinfo(state)->hard_max;
 109 }
 110
 111 void estate_set_hard_max(struct smatch_state *state)
 112 {
 113          get_dinfo(state)->hard_max = 1;
 114 }
 115
 116 void estate_clear_hard_max(struct smatch_state *state)
 117 {
 118          get_dinfo(state)->hard_max = 0;
 119 }
 120
 121 int estate_get_hard_max(struct smatch_state *state, sval_t *sval)
 122 {
 123         if (!state || !get_dinfo(state)->hard_max || !estate_rl(state))
 124                 return 0;
 125         *sval = rl_max(estate_rl(state));
 126         return 1;
 127 }
 128
 129 sval_t estate_min(struct smatch_state *state)
 130 {
 131         return rl_min(estate_rl(state));
 132 }
 133
 134 sval_t estate_max(struct smatch_state *state)
 135 {
 136         return rl_max(estate_rl(state));
 137 }
 138
 139 struct symbol *estate_type(struct smatch_state *state)
 140 {
 141         return rl_max(estate_rl(state)).type;
 142 }
 143
 144 static int rlists_equiv(struct related_list *one, struct related_list *two)
 145 {
 146         struct relation *one_rel;
 147         struct relation *two_rel;
 148
 149         PREPARE_PTR_LIST(one, one_rel);
 150         PREPARE_PTR_LIST(two, two_rel);
 151         for (;;) {
 152                 if (!one_rel && !two_rel)
 153                         return 1;
 154                 if (!one_rel || !two_rel)
 155                         return 0;
 156                 if (one_rel->sym != two_rel->sym)
 157                         return 0;
 158                 if (strcmp(one_rel->name, two_rel->name))
 159                         return 0;
 160                 NEXT_PTR_LIST(one_rel);
 161                 NEXT_PTR_LIST(two_rel);
 162         }
 163         FINISH_PTR_LIST(two_rel);
 164         FINISH_PTR_LIST(one_rel);
 165
 166         return 1;
 167 }
 168
 169 int estates_equiv(struct smatch_state *one, struct smatch_state *two)
 170 {
 171         if (one == two)
 172                 return 1;
 173         if (!rlists_equiv(estate_related(one), estate_related(two)))
 174                 return 0;
 175         if (strcmp(one->name, two->name) == 0)
 176                 return 1;
 177         return 0;
 178 }
 179
 180 int estate_is_whole(struct smatch_state *state)
 181 {
 182         return is_whole_rl(estate_rl(state));
 183 }
 184
 185 int estate_get_single_value(struct smatch_state *state, sval_t *sval)
 186 {
 187         sval_t min, max;
 188
 189         min = rl_min(estate_rl(state));
 190         max = rl_max(estate_rl(state));
 191         if (sval_cmp(min, max) != 0)
 192                 return 0;
 193         *sval = min;
 194         return 1;
 195 }
 196
 197 static struct data_info *alloc_dinfo(void)
 198 {
 199         struct data_info *ret;
 200
 201         ret = __alloc_data_info(0);
 202         memset(ret, 0, sizeof(*ret));
 203         return ret;
 204 }
 205
 206 static struct data_info *alloc_dinfo_range(sval_t min, sval_t max)
 207 {
 208         struct data_info *ret;
 209
 210         ret = alloc_dinfo();
 211         add_range(&ret->value_ranges, min, max);
 212         return ret;
 213 }
 214
 215 static struct data_info *alloc_dinfo_range_list(struct range_list *rl)
 216 {
 217         struct data_info *ret;
 218
 219         ret = alloc_dinfo();
 220         ret->value_ranges = rl;
 221         return ret;
 222 }
 223
 224 static struct data_info *clone_dinfo(struct data_info *dinfo)
 225 {
 226         struct data_info *ret;
 227
 228         ret = alloc_dinfo();
 229         ret->related = clone_related_list(dinfo->related);
 230         ret->value_ranges = clone_rl(dinfo->value_ranges);
 231         ret->hard_max = dinfo->hard_max;
 232         ret->fuzzy_max = dinfo->fuzzy_max;
 233         return ret;
 234 }
 235
 236 struct smatch_state *clone_estate(struct smatch_state *state)
 237 {
 238         struct smatch_state *ret;
 239
 240         ret = __alloc_smatch_state(0);
 241         ret->name = state->name;
 242         ret->data = clone_dinfo(get_dinfo(state));
 243         return ret;
 244 }
 245
 246 struct smatch_state *alloc_estate_empty(void)
 247 {
 248         struct smatch_state *state;
 249         struct data_info *dinfo;
 250
 251         dinfo = alloc_dinfo();
 252         state = __alloc_smatch_state(0);
 253         state->data = dinfo;
 254         state->name = "";
 255         return state;
 256 }
 257
 258 struct smatch_state *alloc_estate_whole(struct symbol *type)
 259 {
 260         return alloc_estate_rl(alloc_whole_rl(type));
 261 }
 262
 263 struct smatch_state *extra_empty(void)
 264 {
 265         struct smatch_state *ret;
 266
 267         ret = __alloc_smatch_state(0);
 268         ret->name = "empty";
 269         ret->data = alloc_dinfo();
 270         return ret;
 271 }
 272
 273 struct smatch_state *alloc_estate_sval(sval_t sval)
 274 {
 275         struct smatch_state *state;
 276
 277         state = __alloc_smatch_state(0);
 278         state->data = alloc_dinfo_range(sval, sval);
 279         state->name = show_rl(get_dinfo(state)->value_ranges);
 280         estate_set_hard_max(state);
 281         estate_set_fuzzy_max(state, sval);
 282         return state;
 283 }
 284
 285 struct smatch_state *alloc_estate_range(sval_t min, sval_t max)
 286 {
 287         struct smatch_state *state;
 288
 289         state = __alloc_smatch_state(0);
 290         state->data = alloc_dinfo_range(min, max);
 291         state->name = show_rl(get_dinfo(state)->value_ranges);
 292         return state;
 293 }
 294
 295 struct smatch_state *alloc_estate_rl(struct range_list *rl)
 296 {
 297         struct smatch_state *state;
 298
 299         if (!rl)
 300                 return extra_empty();
 301
 302         state = __alloc_smatch_state(0);
 303         state->data = alloc_dinfo_range_list(rl);
 304         state->name = show_rl(rl);
 305         return state;
 306 }
 307
 308 struct smatch_state *get_implied_estate(struct expression *expr)
 309 {
 310         struct smatch_state *state;
 311         struct range_list *rl;
 312
 313         state = get_state_expr(SMATCH_EXTRA, expr);
 314         if (state)
 315                 return state;
 316         if (!get_implied_rl(expr, &rl))
 317                 rl = alloc_whole_rl(get_type(expr));
 318         return alloc_estate_rl(rl);
 319 }
 320
 321 struct smatch_state *estate_filter_range(struct smatch_state *orig,
 322                                  sval_t filter_min, sval_t filter_max)
 323 {
 324         struct range_list *rl;
 325         struct smatch_state *state;
 326
 327         if (!orig)
 328                 orig = alloc_estate_whole(filter_min.type);
 329
 330         rl = remove_range(estate_rl(orig), filter_min, filter_max);
 331         state = alloc_estate_rl(rl);
 332         if (estate_has_hard_max(orig))
 333                 estate_set_hard_max(state);
 334         if (estate_has_fuzzy_max(orig))
 335                 estate_set_fuzzy_max(state, estate_get_fuzzy_max(orig));
 336         return state;
 337 }
 338
 339 struct smatch_state *estate_filter_sval(struct smatch_state *orig, sval_t sval)
 340 {
 341         return estate_filter_range(orig, sval, sval);
 342 }
 343
 344