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