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