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