smatch_estate.c

   1 /*
   2  * Copyright (C) 2010 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 /*
  19  * smatch_dinfo.c has helper functions for handling data_info structs
  20  *
  21  */
  22
  23 #include <stdlib.h>
  24 #ifndef __USE_ISOC99
  25 #define __USE_ISOC99
  26 #endif
  27 #include <limits.h>
  28 #include "parse.h"
  29 #include "smatch.h"
  30 #include "smatch_slist.h"
  31 #include "smatch_extra.h"
  32
  33 struct smatch_state *merge_estates(struct smatch_state *s1, struct smatch_state *s2)
  34 {
  35         struct smatch_state *tmp;
  36         struct range_list *value_ranges;
  37         struct related_list *rlist;
  38
  39         if (estates_equiv(s1, s2))
  40                 return s1;
  41
  42         value_ranges = rl_union(estate_rl(s1), estate_rl(s2));
  43         tmp = alloc_estate_rl(value_ranges);
  44         rlist = get_shared_relations(estate_related(s1), estate_related(s2));
  45         set_related(tmp, rlist);
  46
  47         if ((estate_has_hard_max(s1) && (!estate_rl(s2) || estate_has_hard_max(s2))) ||
  48             (estate_has_hard_max(s2) && (!estate_rl(s1) || estate_has_hard_max(s1))))
  49                 estate_set_hard_max(tmp);
  50
  51         estate_set_fuzzy_max(tmp, sval_max(estate_get_fuzzy_max(s1), estate_get_fuzzy_max(s2)));
  52
  53         return tmp;
  54 }
  55
  56 struct data_info *get_dinfo(struct smatch_state *state)
  57 {
  58         if (!state)
  59                 return NULL;
  60         return (struct data_info *)state->data;
  61 }
  62
  63 struct range_list *estate_rl(struct smatch_state *state)
  64 {
  65         if (!state)
  66                 return NULL;
  67         return get_dinfo(state)->value_ranges;
  68 }
  69
  70 struct related_list *estate_related(struct smatch_state *state)
  71 {
  72         if (!state)
  73                 return NULL;
  74         return get_dinfo(state)->related;
  75 }
  76
  77 sval_t estate_get_fuzzy_max(struct smatch_state *state)
  78 {
  79         sval_t empty = {};
  80
  81         if (!state || !get_dinfo(state))
  82                 return empty;
  83         return get_dinfo(state)->fuzzy_max;
  84 }
  85
  86 int estate_has_fuzzy_max(struct smatch_state *state)
  87 {
  88         if (estate_get_fuzzy_max(state).type)
  89                 return 1;
  90         return 0;
  91 }
  92
  93 void estate_set_fuzzy_max(struct smatch_state *state, sval_t fuzzy_max)
  94 {
  95         if (!rl_has_sval(estate_rl(state), fuzzy_max))
  96                 return;
  97         get_dinfo(state)->fuzzy_max = fuzzy_max;
  98 }
  99
 100 void estate_copy_fuzzy_max(struct smatch_state *new, struct smatch_state *old)
 101 {
 102         if (!estate_has_fuzzy_max(old))
 103                 return;
 104         estate_set_fuzzy_max(new, estate_get_fuzzy_max(old));
 105 }
 106
 107 void estate_clear_fuzzy_max(struct smatch_state *state)
 108 {
 109         sval_t empty = {};
 110
 111         get_dinfo(state)->fuzzy_max = empty;
 112 }
 113
 114 int estate_has_hard_max(struct smatch_state *state)
 115 {
 116         if (!state)
 117                 return 0;
 118         return get_dinfo(state)->hard_max;
 119 }
 120
 121 void estate_set_hard_max(struct smatch_state *state)
 122 {
 123         get_dinfo(state)->hard_max = 1;
 124 }
 125
 126 void estate_clear_hard_max(struct smatch_state *state)
 127 {
 128         get_dinfo(state)->hard_max = 0;
 129 }
 130
 131 int estate_get_hard_max(struct smatch_state *state, sval_t *sval)
 132 {
 133         if (!state || !get_dinfo(state)->hard_max || !estate_rl(state))
 134                 return 0;
 135         *sval = rl_max(estate_rl(state));
 136         return 1;
 137 }
 138
 139 sval_t estate_min(struct smatch_state *state)
 140 {
 141         return rl_min(estate_rl(state));
 142 }
 143
 144 sval_t estate_max(struct smatch_state *state)
 145 {
 146         return rl_max(estate_rl(state));
 147 }
 148
 149 struct symbol *estate_type(struct smatch_state *state)
 150 {
 151         return rl_max(estate_rl(state)).type;
 152 }
 153
 154 static int rlists_equiv(struct related_list *one, struct related_list *two)
 155 {
 156         struct relation *one_rel;
 157         struct relation *two_rel;
 158
 159         PREPARE_PTR_LIST(one, one_rel);
 160         PREPARE_PTR_LIST(two, two_rel);
 161         for (;;) {
 162                 if (!one_rel && !two_rel)
 163                         return 1;
 164                 if (!one_rel || !two_rel)
 165                         return 0;
 166                 if (one_rel->sym != two_rel->sym)
 167                         return 0;
 168                 if (strcmp(one_rel->name, two_rel->name))
 169                         return 0;
 170                 NEXT_PTR_LIST(one_rel);
 171                 NEXT_PTR_LIST(two_rel);
 172         }
 173         FINISH_PTR_LIST(two_rel);
 174         FINISH_PTR_LIST(one_rel);
 175
 176         return 1;
 177 }
 178
 179 int estates_equiv(struct smatch_state *one, struct smatch_state *two)
 180 {
 181         if (!one || !two)
 182                 return 0;
 183         if (one == two)
 184                 return 1;
 185         if (!rlists_equiv(estate_related(one), estate_related(two)))
 186                 return 0;
 187         if (strcmp(one->name, two->name) == 0)
 188                 return 1;
 189         return 0;
 190 }
 191
 192 int estate_is_whole(struct smatch_state *state)
 193 {
 194         return is_whole_rl(estate_rl(state));
 195 }
 196
 197 int estate_is_empty(struct smatch_state *state)
 198 {
 199         return state && !estate_rl(state);
 200 }
 201
 202 int estate_is_unknown(struct smatch_state *state)
 203 {
 204         if (!estate_is_whole(state))
 205                 return 0;
 206         if (estate_related(state))
 207                 return 0;
 208         if (estate_has_fuzzy_max(state))
 209                 return 0;
 210         return 1;
 211 }
 212
 213 int estate_get_single_value(struct smatch_state *state, sval_t *sval)
 214 {
 215         sval_t min, max;
 216
 217         min = rl_min(estate_rl(state));
 218         max = rl_max(estate_rl(state));
 219         if (sval_cmp(min, max) != 0)
 220                 return 0;
 221         *sval = min;
 222         return 1;
 223 }
 224
 225 static struct data_info *alloc_dinfo(void)
 226 {
 227         struct data_info *ret;
 228
 229         ret = __alloc_data_info(0);
 230         memset(ret, 0, sizeof(*ret));
 231         return ret;
 232 }
 233
 234 static struct data_info *alloc_dinfo_range(sval_t min, sval_t max)
 235 {
 236         struct data_info *ret;
 237
 238         ret = alloc_dinfo();
 239         add_range(&ret->value_ranges, min, max);
 240         return ret;
 241 }
 242
 243 static struct data_info *alloc_dinfo_range_list(struct range_list *rl)
 244 {
 245         struct data_info *ret;
 246
 247         ret = alloc_dinfo();
 248         ret->value_ranges = rl;
 249         return ret;
 250 }
 251
 252 static struct data_info *clone_dinfo(struct data_info *dinfo)
 253 {
 254         struct data_info *ret;
 255
 256         ret = alloc_dinfo();
 257         ret->related = clone_related_list(dinfo->related);
 258         ret->value_ranges = clone_rl(dinfo->value_ranges);
 259         ret->hard_max = dinfo->hard_max;
 260         ret->fuzzy_max = dinfo->fuzzy_max;
 261         return ret;
 262 }
 263
 264 struct smatch_state *clone_estate(struct smatch_state *state)
 265 {
 266         struct smatch_state *ret;
 267
 268         if (!state)
 269                 return NULL;
 270
 271         ret = __alloc_smatch_state(0);
 272         ret->name = state->name;
 273         ret->data = clone_dinfo(get_dinfo(state));
 274         return ret;
 275 }
 276
 277 struct smatch_state *alloc_estate_empty(void)
 278 {
 279         struct smatch_state *state;
 280         struct data_info *dinfo;
 281
 282         dinfo = alloc_dinfo();
 283         state = __alloc_smatch_state(0);
 284         state->data = dinfo;
 285         state->name = "";
 286         return state;
 287 }
 288
 289 struct smatch_state *alloc_estate_whole(struct symbol *type)
 290 {
 291         return alloc_estate_rl(alloc_whole_rl(type));
 292 }
 293
 294 struct smatch_state *extra_empty(void)
 295 {
 296         struct smatch_state *ret;
 297
 298         ret = __alloc_smatch_state(0);
 299         ret->name = "empty";
 300         ret->data = alloc_dinfo();
 301         return ret;
 302 }
 303
 304 struct smatch_state *alloc_estate_sval(sval_t sval)
 305 {
 306         struct smatch_state *state;
 307
 308         state = __alloc_smatch_state(0);
 309         state->data = alloc_dinfo_range(sval, sval);
 310         state->name = show_rl(get_dinfo(state)->value_ranges);
 311         estate_set_hard_max(state);
 312         estate_set_fuzzy_max(state, sval);
 313         return state;
 314 }
 315
 316 struct smatch_state *alloc_estate_range(sval_t min, sval_t max)
 317 {
 318         struct smatch_state *state;
 319
 320         state = __alloc_smatch_state(0);
 321         state->data = alloc_dinfo_range(min, max);
 322         state->name = show_rl(get_dinfo(state)->value_ranges);
 323         return state;
 324 }
 325
 326 struct smatch_state *alloc_estate_rl(struct range_list *rl)
 327 {
 328         struct smatch_state *state;
 329
 330         if (!rl)
 331                 return extra_empty();
 332
 333         state = __alloc_smatch_state(0);
 334         state->data = alloc_dinfo_range_list(rl);
 335         state->name = show_rl(rl);
 336         return state;
 337 }
 338
 339 struct smatch_state *clone_estate_cast(struct symbol *type, struct smatch_state *state)
 340 {
 341         struct smatch_state *ret;
 342         struct data_info *dinfo;
 343
 344         if (!state)
 345                 return NULL;
 346
 347         dinfo = alloc_dinfo();
 348         dinfo->value_ranges = clone_rl(cast_rl(type, estate_rl(state)));
 349
 350         ret = __alloc_smatch_state(0);
 351         ret->name = show_rl(dinfo->value_ranges);
 352         ret->data = dinfo;
 353
 354         return ret;
 355 }
 356
 357 struct smatch_state *get_implied_estate(struct expression *expr)
 358 {
 359         struct smatch_state *state;
 360         struct range_list *rl;
 361
 362         state = get_state_expr(SMATCH_EXTRA, expr);
 363         if (state)
 364                 return state;
 365         if (!get_implied_rl(expr, &rl))
 366                 rl = alloc_whole_rl(get_type(expr));
 367         return alloc_estate_rl(rl);
 368 }
 369
 370 struct smatch_state *estate_filter_range(struct smatch_state *orig,
 371                                  sval_t filter_min, sval_t filter_max)
 372 {
 373         struct range_list *rl;
 374         struct smatch_state *state;
 375
 376         if (!orig)
 377                 orig = alloc_estate_whole(filter_min.type);
 378
 379         rl = remove_range(estate_rl(orig), filter_min, filter_max);
 380         state = alloc_estate_rl(rl);
 381         if (estate_has_hard_max(orig))
 382                 estate_set_hard_max(state);
 383         if (estate_has_fuzzy_max(orig))
 384                 estate_set_fuzzy_max(state, estate_get_fuzzy_max(orig));
 385         return state;
 386 }
 387
 388 struct smatch_state *estate_filter_sval(struct smatch_state *orig, sval_t sval)
 389 {
 390         return estate_filter_range(orig, sval, sval);
 391 }
 392
 393 /*
 394  * One of the complications is that smatch tries to free a bunch of data at the
 395  * end of every function.
 396  */
 397 struct data_info *clone_dinfo_perm(struct data_info *dinfo)
 398 {
 399         struct data_info *ret;
 400
 401         ret = malloc(sizeof(*ret));
 402         memset(ret, 0, sizeof(*ret));
 403         ret->related = NULL;
 404         ret->value_ranges = clone_rl_permanent(dinfo->value_ranges);
 405         ret->hard_max = 0;
 406         ret->fuzzy_max = dinfo->fuzzy_max;
 407         return ret;
 408 }
 409
 410 struct smatch_state *clone_estate_perm(struct smatch_state *state)
 411 {
 412         struct smatch_state *ret;
 413
 414         ret = malloc(sizeof(*ret));
 415         ret->name = alloc_string(state->name);
 416         ret->data = clone_dinfo_perm(get_dinfo(state));
 417         return ret;
 418 }
 419
 420