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