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