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