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