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