real_absolute: += and = are not the same
[smatch.git] / smatch_math.c
blob90720aaaa07ff33ce261c8c5194aee84a8131258
1 /*
2 * Copyright (C) 2010 Dan Carpenter.
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.
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.
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
18 #include "symbol.h"
19 #include "smatch.h"
20 #include "smatch_slist.h"
21 #include "smatch_extra.h"
23 static struct range_list *_get_rl(struct expression *expr, int implied, int *recurse_cnt);
24 static struct range_list *handle_variable(struct expression *expr, int implied, int *recurse_cnt);
25 static struct range_list *(*custom_handle_variable)(struct expression *expr);
27 static int get_implied_value_internal(struct expression *expr, sval_t *sval, int *recurse_cnt);
28 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
30 static sval_t zero = {.type = &int_ctype, {.value = 0} };
31 static sval_t one = {.type = &int_ctype, {.value = 1} };
33 struct range_list *rl_zero(void)
35 return alloc_rl(zero, zero);
38 struct range_list *rl_one(void)
40 return alloc_rl(one, one);
43 enum {
44 RL_EXACT,
45 RL_HARD,
46 RL_FUZZY,
47 RL_IMPLIED,
48 RL_ABSOLUTE,
49 RL_REAL_ABSOLUTE,
52 static struct range_list *last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt)
54 if (!stmt)
55 return NULL;
57 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
58 if (stmt->type != STMT_EXPRESSION)
59 return NULL;
60 return _get_rl(stmt->expression, implied, recurse_cnt);
63 static struct range_list *handle_expression_statement_rl(struct expression *expr, int implied, int *recurse_cnt)
65 return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt);
68 static struct range_list *handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt)
70 struct range_list *rl;
72 if (implied == RL_EXACT || implied == RL_HARD)
73 return NULL;
74 if (get_address_rl(expr, &rl))
75 return rl;
76 return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
79 static struct range_list *handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt)
81 if (known_condition_true(expr->unop))
82 return rl_zero();
83 if (known_condition_false(expr->unop))
84 return rl_one();
86 if (implied == RL_EXACT)
87 return NULL;
89 if (implied_condition_true(expr->unop))
90 return rl_zero();
91 if (implied_condition_false(expr->unop))
92 return rl_one();
93 return alloc_rl(zero, one);
96 static struct range_list *handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt)
98 struct range_list *rl;
99 sval_t sval;
101 rl = _get_rl(expr->unop, implied, recurse_cnt);
102 if (!rl_to_sval(rl, &sval))
103 return NULL;
104 sval = sval_preop(sval, '~');
105 sval_cast(get_type(expr->unop), sval);
106 return alloc_rl(sval, sval);
109 static struct range_list *handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt)
111 struct range_list *rl;
112 sval_t sval;
114 rl = _get_rl(expr->unop, implied, recurse_cnt);
115 if (!rl_to_sval(rl, &sval))
116 return NULL;
117 sval = sval_preop(sval, '-');
118 return alloc_rl(sval, sval);
121 static struct range_list *handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt)
123 switch (expr->op) {
124 case '&':
125 return handle_ampersand_rl(expr, implied, recurse_cnt);
126 case '!':
127 return handle_negate_rl(expr, implied, recurse_cnt);
128 case '~':
129 return handle_bitwise_negate(expr, implied, recurse_cnt);
130 case '-':
131 return handle_minus_preop(expr, implied, recurse_cnt);
132 case '*':
133 return handle_variable(expr, implied, recurse_cnt);
134 case '(':
135 return handle_expression_statement_rl(expr, implied, recurse_cnt);
136 default:
137 return NULL;
141 static struct range_list *handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt)
143 struct range_list *left_rl, *right_rl;
144 struct symbol *type;
146 type = get_type(expr);
148 left_rl = _get_rl(expr->left, implied, recurse_cnt);
149 left_rl = cast_rl(type, left_rl);
150 right_rl = _get_rl(expr->right, implied, recurse_cnt);
151 right_rl = cast_rl(type, right_rl);
153 if (!left_rl || !right_rl)
154 return NULL;
156 if (implied != RL_REAL_ABSOLUTE) {
157 if (is_whole_rl(left_rl) || is_whole_rl(right_rl))
158 return NULL;
161 return rl_binop(left_rl, '/', right_rl);
164 static struct range_list *handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt)
166 struct symbol *type;
167 struct range_list *left_rl, *right_rl;
168 sval_t max, min, tmp;
169 int comparison;
171 type = get_type(expr);
172 comparison = get_comparison(expr->left, expr->right);
174 left_rl = _get_rl(expr->left, implied, recurse_cnt);
175 left_rl = cast_rl(type, left_rl);
176 right_rl = _get_rl(expr->right, implied, recurse_cnt);
177 right_rl = cast_rl(type, right_rl);
179 if ((!left_rl || !right_rl) &&
180 (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY))
181 return NULL;
183 if (!left_rl)
184 left_rl = alloc_whole_rl(type);
185 if (!right_rl)
186 right_rl = alloc_whole_rl(type);
188 /* negative values complicate everything fix this later */
189 if (sval_is_negative(rl_min(right_rl)))
190 return NULL;
191 max = rl_max(left_rl);
193 switch (comparison) {
194 case '>':
195 case SPECIAL_UNSIGNED_GT:
196 min = sval_type_val(type, 1);
197 max = rl_max(left_rl);
198 break;
199 case SPECIAL_GTE:
200 case SPECIAL_UNSIGNED_GTE:
201 min = sval_type_val(type, 0);
202 max = rl_max(left_rl);
203 break;
204 default:
205 if (sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl)))
206 return NULL;
207 min = sval_type_min(type);
210 if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
211 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
212 if (sval_cmp(tmp, min) > 0)
213 min = tmp;
216 if (!sval_is_max(rl_max(left_rl))) {
217 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
218 if (sval_cmp(tmp, max) < 0)
219 max = tmp;
222 if (sval_is_min(min) && sval_is_max(max))
223 return NULL;
225 return cast_rl(type, alloc_rl(min, max));
228 static struct range_list *handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt)
230 struct range_list *rl;
231 sval_t left, right, sval;
233 if (implied == RL_EXACT) {
234 if (!get_value(expr->right, &right))
235 return NULL;
236 if (!get_value(expr->left, &left))
237 return NULL;
238 sval = sval_binop(left, '%', right);
239 return alloc_rl(sval, sval);
241 /* if we can't figure out the right side it's probably hopeless */
242 if (!get_implied_value_internal(expr->right, &right, recurse_cnt))
243 return NULL;
245 right = sval_cast(get_type(expr), right);
246 right.value--;
248 rl = _get_rl(expr->left, implied, recurse_cnt);
249 if (rl && rl_max(rl).uvalue < right.uvalue)
250 right.uvalue = rl_max(rl).uvalue;
252 return alloc_rl(zero, right);
255 static sval_t sval_lowest_set_bit(sval_t sval)
257 int i;
258 int found = 0;
260 for (i = 0; i < 64; i++) {
261 if (sval.uvalue & 1ULL << i) {
262 if (!found++)
263 continue;
264 sval.uvalue &= ~(1ULL << i);
267 return sval;
270 static struct range_list *handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt)
272 struct symbol *type;
273 struct range_list *left_rl, *right_rl;
274 sval_t known;
276 if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
277 return NULL;
279 type = get_type(expr);
281 if (get_implied_value_internal(expr->left, &known, recurse_cnt)) {
282 sval_t min;
284 min = sval_lowest_set_bit(known);
285 left_rl = alloc_rl(min, known);
286 left_rl = cast_rl(type, left_rl);
287 add_range(&left_rl, sval_type_val(type, 0), sval_type_val(type, 0));
288 } else {
289 left_rl = _get_rl(expr->left, implied, recurse_cnt);
290 if (left_rl) {
291 left_rl = cast_rl(type, left_rl);
292 left_rl = alloc_rl(sval_type_val(type, 0), rl_max(left_rl));
293 } else {
294 if (implied == RL_HARD)
295 return NULL;
296 left_rl = alloc_whole_rl(type);
300 if (get_implied_value_internal(expr->right, &known, recurse_cnt)) {
301 sval_t min, left_max, mod;
303 min = sval_lowest_set_bit(known);
304 right_rl = alloc_rl(min, known);
305 right_rl = cast_rl(type, right_rl);
306 add_range(&right_rl, sval_type_val(type, 0), sval_type_val(type, 0));
308 if (min.value != 0) {
309 left_max = rl_max(left_rl);
310 mod = sval_binop(left_max, '%', min);
311 if (mod.value) {
312 left_max = sval_binop(left_max, '-', mod);
313 left_max.value++;
314 if (left_max.value > 0 && sval_cmp(left_max, rl_max(left_rl)) < 0)
315 left_rl = remove_range(left_rl, left_max, rl_max(left_rl));
318 } else {
319 right_rl = _get_rl(expr->right, implied, recurse_cnt);
320 if (right_rl) {
321 right_rl = cast_rl(type, right_rl);
322 right_rl = alloc_rl(sval_type_val(type, 0), rl_max(right_rl));
323 } else {
324 if (implied == RL_HARD)
325 return NULL;
326 right_rl = alloc_whole_rl(type);
330 return rl_intersection(left_rl, right_rl);
333 static struct range_list *use_rl_binop(struct expression *expr, int implied, int *recurse_cnt)
335 struct symbol *type;
336 struct range_list *left_rl, *right_rl;
338 if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
339 return NULL;
341 type = get_type(expr);
343 get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt);
344 get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt);
345 left_rl = cast_rl(type, left_rl);
346 right_rl = cast_rl(type, right_rl);
347 if (!left_rl || !right_rl)
348 return NULL;
350 return rl_binop(left_rl, expr->op, right_rl);
353 static struct range_list *handle_right_shift(struct expression *expr, int implied, int *recurse_cnt)
355 struct range_list *left_rl;
356 sval_t right;
357 sval_t min, max;
359 if (implied == RL_EXACT || implied == RL_HARD)
360 return NULL;
362 left_rl = _get_rl(expr->left, implied, recurse_cnt);
363 if (left_rl) {
364 max = rl_max(left_rl);
365 min = rl_min(left_rl);
366 } else {
367 if (implied == RL_FUZZY)
368 return NULL;
369 max = sval_type_max(get_type(expr->left));
370 min = sval_type_val(get_type(expr->left), 0);
373 if (get_implied_value_internal(expr->right, &right, recurse_cnt)) {
374 min = sval_binop(min, SPECIAL_RIGHTSHIFT, right);
375 max = sval_binop(max, SPECIAL_RIGHTSHIFT, right);
376 } else if (!sval_is_negative(min)) {
377 min.value = 0;
378 max = sval_type_max(max.type);
379 } else {
380 return NULL;
383 return alloc_rl(min, max);
386 static struct range_list *handle_left_shift(struct expression *expr, int implied, int *recurse_cnt)
388 struct range_list *left_rl, *res;
389 sval_t right;
390 sval_t min, max;
391 int add_zero = 0;
393 if (implied == RL_EXACT || implied == RL_HARD)
394 return NULL;
395 /* this is hopeless without the right side */
396 if (!get_implied_value_internal(expr->right, &right, recurse_cnt))
397 return NULL;
398 left_rl = _get_rl(expr->left, implied, recurse_cnt);
399 if (left_rl) {
400 max = rl_max(left_rl);
401 min = rl_min(left_rl);
402 if (min.value == 0) {
403 min.value = 1;
404 add_zero = 1;
406 } else {
407 if (implied == RL_FUZZY)
408 return NULL;
409 max = sval_type_max(get_type(expr->left));
410 min = sval_type_val(get_type(expr->left), 1);
411 add_zero = 1;
414 max = sval_binop(max, SPECIAL_LEFTSHIFT, right);
415 min = sval_binop(min, SPECIAL_LEFTSHIFT, right);
416 res = alloc_rl(min, max);
417 if (add_zero)
418 res = rl_union(res, rl_zero());
419 return res;
422 static struct range_list *handle_known_binop(struct expression *expr)
424 sval_t left, right;
426 if (!get_value(expr->left, &left))
427 return NULL;
428 if (!get_value(expr->right, &right))
429 return NULL;
430 left = sval_binop(left, expr->op, right);
431 return alloc_rl(left, left);
434 static int has_actual_ranges(struct range_list *rl)
436 struct data_range *tmp;
438 FOR_EACH_PTR(rl, tmp) {
439 if (sval_cmp(tmp->min, tmp->max) != 0)
440 return 1;
441 } END_FOR_EACH_PTR(tmp);
442 return 0;
445 static struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl)
447 struct range_list *res_rl;
448 struct data_range *left_drange, *right_drange;
449 sval_t res;
451 if (!left_rl || !right_rl)
452 return NULL;
453 if (has_actual_ranges(left_rl))
454 return NULL;
455 if (has_actual_ranges(right_rl))
456 return NULL;
458 if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20)
459 return NULL;
461 res_rl = NULL;
463 FOR_EACH_PTR(left_rl, left_drange) {
464 FOR_EACH_PTR(right_rl, right_drange) {
465 if ((op == '%' || op == '/') &&
466 right_drange->min.value == 0)
467 return NULL;
468 res = sval_binop(left_drange->min, op, right_drange->min);
469 add_range(&res_rl, res, res);
470 } END_FOR_EACH_PTR(right_drange);
471 } END_FOR_EACH_PTR(left_drange);
473 return res_rl;
476 static struct range_list *handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt)
478 struct smatch_state *state;
479 struct symbol *type;
480 struct range_list *left_rl, *right_rl, *rl;
481 sval_t min, max;
483 rl = handle_known_binop(expr);
484 if (rl)
485 return rl;
486 if (implied == RL_EXACT)
487 return NULL;
489 state = get_extra_state(expr);
490 if (state && !is_whole_rl(estate_rl(state)))
491 return clone_rl(estate_rl(state));
493 type = get_type(expr);
494 left_rl = _get_rl(expr->left, implied, recurse_cnt);
495 left_rl = cast_rl(type, left_rl);
496 right_rl = _get_rl(expr->right, implied, recurse_cnt);
497 right_rl = cast_rl(type, right_rl);
499 if (!left_rl && !right_rl)
500 return NULL;
502 rl = handle_implied_binop(left_rl, expr->op, right_rl);
503 if (rl)
504 return rl;
506 switch (expr->op) {
507 case '%':
508 return handle_mod_rl(expr, implied, recurse_cnt);
509 case '&':
510 return handle_bitwise_AND(expr, implied, recurse_cnt);
511 case '|':
512 case '^':
513 return use_rl_binop(expr, implied, recurse_cnt);
514 case SPECIAL_RIGHTSHIFT:
515 return handle_right_shift(expr, implied, recurse_cnt);
516 case SPECIAL_LEFTSHIFT:
517 return handle_left_shift(expr, implied, recurse_cnt);
518 case '-':
519 return handle_subtract_rl(expr, implied, recurse_cnt);
520 case '/':
521 return handle_divide_rl(expr, implied, recurse_cnt);
524 if (!left_rl || !right_rl)
525 return NULL;
527 if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
528 return NULL;
529 if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl)))
530 return NULL;
532 min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
533 max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
535 return alloc_rl(min, max);
538 static int do_comparison(struct expression *expr)
540 struct range_list *left_ranges = NULL;
541 struct range_list *right_ranges = NULL;
542 int poss_true, poss_false;
543 struct symbol *type;
545 type = get_type(expr);
546 get_absolute_rl(expr->left, &left_ranges);
547 get_absolute_rl(expr->right, &right_ranges);
549 left_ranges = cast_rl(type, left_ranges);
550 right_ranges = cast_rl(type, right_ranges);
552 poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
553 poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
555 free_rl(&left_ranges);
556 free_rl(&right_ranges);
558 if (!poss_true && !poss_false)
559 return 0x0;
560 if (poss_true && !poss_false)
561 return 0x1;
562 if (!poss_true && poss_false)
563 return 0x2;
564 return 0x3;
567 static struct range_list *handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt)
569 sval_t left, right;
570 int res;
572 if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
573 struct data_range tmp_left, tmp_right;
575 tmp_left.min = left;
576 tmp_left.max = left;
577 tmp_right.min = right;
578 tmp_right.max = right;
579 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
580 return rl_one();
581 return rl_zero();
584 if (implied == RL_EXACT)
585 return NULL;
587 res = do_comparison(expr);
588 if (res == 1)
589 return rl_one();
590 if (res == 2)
591 return rl_zero();
593 return alloc_rl(zero, one);
596 static struct range_list *handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt)
598 sval_t left, right;
599 int left_known = 0;
600 int right_known = 0;
602 if (implied == RL_EXACT) {
603 if (get_value(expr->left, &left))
604 left_known = 1;
605 if (get_value(expr->right, &right))
606 right_known = 1;
607 } else {
608 if (get_implied_value_internal(expr->left, &left, recurse_cnt))
609 left_known = 1;
610 if (get_implied_value_internal(expr->right, &right, recurse_cnt))
611 right_known = 1;
614 switch (expr->op) {
615 case SPECIAL_LOGICAL_OR:
616 if (left_known && left.value)
617 return rl_one();
618 if (right_known && right.value)
619 return rl_one();
620 if (left_known && right_known)
621 return rl_zero();
622 break;
623 case SPECIAL_LOGICAL_AND:
624 if (left_known && right_known) {
625 if (left.value && right.value)
626 return rl_one();
627 return rl_zero();
629 break;
630 default:
631 return NULL;
634 if (implied == RL_EXACT)
635 return NULL;
637 return alloc_rl(zero, one);
640 static struct range_list *handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt)
642 struct range_list *true_rl, *false_rl;
643 struct symbol *type;
644 int final_pass_orig = final_pass;
646 if (known_condition_true(expr->conditional))
647 return _get_rl(expr->cond_true, implied, recurse_cnt);
648 if (known_condition_false(expr->conditional))
649 return _get_rl(expr->cond_false, implied, recurse_cnt);
651 if (implied == RL_EXACT)
652 return NULL;
654 if (implied_condition_true(expr->conditional))
655 return _get_rl(expr->cond_true, implied, recurse_cnt);
656 if (implied_condition_false(expr->conditional))
657 return _get_rl(expr->cond_false, implied, recurse_cnt);
660 /* this becomes a problem with deeply nested conditional statements */
661 if (low_on_memory())
662 return NULL;
664 type = get_type(expr);
666 __push_fake_cur_stree();
667 final_pass = 0;
668 __split_whole_condition(expr->conditional);
669 true_rl = _get_rl(expr->cond_true, implied, recurse_cnt);
670 __push_true_states();
671 __use_false_states();
672 false_rl = _get_rl(expr->cond_false, implied, recurse_cnt);
673 __merge_true_states();
674 __free_fake_cur_stree();
675 final_pass = final_pass_orig;
677 if (!true_rl || !false_rl)
678 return NULL;
679 true_rl = cast_rl(type, true_rl);
680 false_rl = cast_rl(type, false_rl);
682 return rl_union(true_rl, false_rl);
685 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
687 struct smatch_state *state;
688 sval_t sval;
690 if (get_hard_max(expr, &sval)) {
691 *max = sval;
692 return 1;
695 state = get_extra_state(expr);
696 if (!state || !estate_has_fuzzy_max(state))
697 return 0;
698 *max = sval_cast(get_type(expr), estate_get_fuzzy_max(state));
699 return 1;
702 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
704 struct smatch_state *state;
705 sval_t sval;
707 state = get_extra_state(expr);
708 if (!state || !estate_rl(state))
709 return 0;
711 sval = estate_min(state);
712 if (sval_is_negative(sval) && sval_is_min(sval))
713 return 0;
715 if (sval_is_max(sval))
716 return 0;
718 *min = sval_cast(get_type(expr), sval);
719 return 1;
722 int get_const_value(struct expression *expr, sval_t *sval)
724 struct symbol *sym;
725 sval_t right;
727 if (expr->type != EXPR_SYMBOL || !expr->symbol)
728 return 0;
729 sym = expr->symbol;
730 if (!(sym->ctype.modifiers & MOD_CONST))
731 return 0;
732 if (get_value(sym->initializer, &right)) {
733 *sval = sval_cast(get_type(expr), right);
734 return 1;
736 return 0;
739 struct range_list *var_to_absolute_rl(struct expression *expr)
741 struct smatch_state *state;
742 struct range_list *rl;
744 state = get_extra_state(expr);
745 if (!state || is_whole_rl(estate_rl(state))) {
746 state = get_real_absolute_state(expr);
747 if (state && state->data && !estate_is_whole(state))
748 return clone_rl(estate_rl(state));
749 if (get_local_rl(expr, &rl) && !is_whole_rl(rl))
750 return rl;
751 if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
752 return rl;
753 return alloc_whole_rl(get_type(expr));
755 /* err on the side of saying things are possible */
756 if (!estate_rl(state))
757 return alloc_whole_rl(get_type(expr));
758 return clone_rl(estate_rl(state));
761 static struct range_list *handle_variable(struct expression *expr, int implied, int *recurse_cnt)
763 struct smatch_state *state;
764 struct range_list *rl;
765 sval_t sval, min, max;
767 if (get_const_value(expr, &sval))
768 return alloc_rl(sval, sval);
770 if (custom_handle_variable) {
771 rl = custom_handle_variable(expr);
772 if (!rl)
773 return var_to_absolute_rl(expr);
774 return rl;
777 switch (implied) {
778 case RL_EXACT:
779 return NULL;
780 case RL_HARD:
781 case RL_IMPLIED:
782 case RL_ABSOLUTE:
783 state = get_extra_state(expr);
784 if (!state || !state->data) {
785 if (implied == RL_HARD)
786 return NULL;
787 if (get_local_rl(expr, &rl))
788 return rl;
789 if (get_db_type_rl(expr, &rl))
790 return rl;
791 return NULL;
793 if (implied == RL_HARD && !estate_has_hard_max(state))
794 return NULL;
795 return clone_rl(estate_rl(state));
796 case RL_REAL_ABSOLUTE:
797 state = get_extra_state(expr);
798 if (!state || !state->data || is_whole_rl(estate_rl(state))) {
799 if (get_local_rl(expr, &rl))
800 return rl;
801 if (get_db_type_rl(expr, &rl))
802 return rl;
803 state = get_real_absolute_state(expr);
804 if (state && state->data)
805 return clone_rl(estate_rl(state));
806 return NULL;
808 return clone_rl(estate_rl(state));
809 case RL_FUZZY:
810 if (!get_fuzzy_min_helper(expr, &min))
811 min = sval_type_min(get_type(expr));
812 if (!get_fuzzy_max_helper(expr, &max))
813 return NULL;
814 /* fuzzy ranges are often inverted */
815 if (sval_cmp(min, max) > 0) {
816 sval = min;
817 min = max;
818 max = sval;
820 return alloc_rl(min, max);
822 return NULL;
825 static sval_t handle_sizeof(struct expression *expr)
827 struct symbol *sym;
828 sval_t ret;
830 ret = sval_blank(expr);
831 sym = expr->cast_type;
832 if (!sym) {
833 sym = evaluate_expression(expr->cast_expression);
835 * Expressions of restricted types will possibly get
836 * promoted - check that here
838 if (is_restricted_type(sym)) {
839 if (type_bits(sym) < bits_in_int)
840 sym = &int_ctype;
841 } else if (is_fouled_type(sym)) {
842 sym = &int_ctype;
845 examine_symbol_type(sym);
847 ret.type = size_t_ctype;
848 if (type_bits(sym) <= 0) /* sizeof(void) */ {
849 if (get_real_base_type(sym) == &void_ctype)
850 ret.value = 1;
851 else
852 ret.value = 0;
853 } else
854 ret.value = type_bytes(sym);
856 return ret;
859 static struct range_list *handle_strlen(struct expression *expr, int implied, int *recurse_cnt)
861 struct range_list *rl;
862 struct expression *arg;
863 sval_t sval = { .type = &ulong_ctype };
865 if (implied == RL_EXACT)
866 return NULL;
868 arg = get_argument_from_call_expr(expr->args, 0);
869 if (!arg)
870 return NULL;
871 if (arg->type == EXPR_STRING) {
872 sval.value = arg->string->length - 1;
873 return alloc_rl(sval, sval);
876 if (implied == RL_HARD || implied == RL_FUZZY)
877 return NULL;
879 if (get_implied_return(expr, &rl))
880 return rl;
882 return NULL;
885 static struct range_list *handle_call_rl(struct expression *expr, int implied, int *recurse_cnt)
887 struct range_list *rl;
889 if (sym_name_is("__builtin_expect", expr->fn)) {
890 struct expression *arg;
892 arg = get_argument_from_call_expr(expr->args, 0);
893 return _get_rl(arg, implied, recurse_cnt);
896 if (sym_name_is("strlen", expr->fn))
897 return handle_strlen(expr, implied, recurse_cnt);
899 if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)
900 return NULL;
902 if (get_implied_return(expr, &rl))
903 return rl;
904 return db_return_vals(expr);
907 static struct range_list *handle_cast(struct expression *expr, int implied, int *recurse_cnt)
909 struct range_list *rl;
910 struct symbol *type;
912 type = get_type(expr);
913 rl = _get_rl(expr->cast_expression, implied, recurse_cnt);
914 if (rl)
915 return cast_rl(type, rl);
916 if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)
917 return alloc_whole_rl(type);
918 if (implied == RL_IMPLIED && type &&
919 type_bits(type) > 0 && type_bits(type) < 32)
920 return alloc_whole_rl(type);
921 return NULL;
924 static struct range_list *_get_rl(struct expression *expr, int implied, int *recurse_cnt)
926 struct range_list *rl;
927 struct symbol *type;
928 sval_t sval;
930 type = get_type(expr);
931 expr = strip_parens(expr);
932 if (!expr)
933 return NULL;
935 if (++(*recurse_cnt) >= 200)
936 return NULL;
938 switch(expr->type) {
939 case EXPR_CAST:
940 case EXPR_FORCE_CAST:
941 case EXPR_IMPLIED_CAST:
942 rl = handle_cast(expr, implied, recurse_cnt);
943 goto out_cast;
946 expr = strip_expr(expr);
947 if (!expr)
948 return NULL;
950 switch (expr->type) {
951 case EXPR_VALUE:
952 sval = sval_from_val(expr, expr->value);
953 rl = alloc_rl(sval, sval);
954 break;
955 case EXPR_PREOP:
956 rl = handle_preop_rl(expr, implied, recurse_cnt);
957 break;
958 case EXPR_POSTOP:
959 rl = _get_rl(expr->unop, implied, recurse_cnt);
960 break;
961 case EXPR_BINOP:
962 rl = handle_binop_rl(expr, implied, recurse_cnt);
963 break;
964 case EXPR_COMPARE:
965 rl = handle_comparison_rl(expr, implied, recurse_cnt);
966 break;
967 case EXPR_LOGICAL:
968 rl = handle_logical_rl(expr, implied, recurse_cnt);
969 break;
970 case EXPR_PTRSIZEOF:
971 case EXPR_SIZEOF:
972 sval = handle_sizeof(expr);
973 rl = alloc_rl(sval, sval);
974 break;
975 case EXPR_SELECT:
976 case EXPR_CONDITIONAL:
977 rl = handle_conditional_rl(expr, implied, recurse_cnt);
978 break;
979 case EXPR_CALL:
980 rl = handle_call_rl(expr, implied, recurse_cnt);
981 break;
982 default:
983 rl = handle_variable(expr, implied, recurse_cnt);
986 out_cast:
987 if (rl)
988 return rl;
989 if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE))
990 return alloc_whole_rl(type);
991 return NULL;
994 /* returns 1 if it can get a value literal or else returns 0 */
995 int get_value(struct expression *expr, sval_t *sval)
997 struct range_list *rl;
998 int recurse_cnt = 0;
1000 rl = _get_rl(expr, RL_EXACT, &recurse_cnt);
1001 if (!rl_to_sval(rl, sval))
1002 return 0;
1003 return 1;
1006 static int get_implied_value_internal(struct expression *expr, sval_t *sval, int *recurse_cnt)
1008 struct range_list *rl;
1010 rl = _get_rl(expr, RL_IMPLIED, recurse_cnt);
1011 if (!rl_to_sval(rl, sval))
1012 return 0;
1013 return 1;
1016 int get_implied_value(struct expression *expr, sval_t *sval)
1018 struct range_list *rl;
1019 int recurse_cnt = 0;
1021 rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1022 if (!rl_to_sval(rl, sval))
1023 return 0;
1024 return 1;
1027 int get_implied_min(struct expression *expr, sval_t *sval)
1029 struct range_list *rl;
1030 int recurse_cnt = 0;
1032 rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1033 if (!rl)
1034 return 0;
1035 *sval = rl_min(rl);
1036 return 1;
1039 int get_implied_max(struct expression *expr, sval_t *sval)
1041 struct range_list *rl;
1042 int recurse_cnt = 0;
1044 rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1045 if (!rl)
1046 return 0;
1047 *sval = rl_max(rl);
1048 return 1;
1051 int get_implied_rl(struct expression *expr, struct range_list **rl)
1053 int recurse_cnt = 0;
1055 *rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1056 if (*rl)
1057 return 1;
1058 return 0;
1061 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt)
1063 *rl = _get_rl(expr, RL_ABSOLUTE, recurse_cnt);
1064 if (!*rl)
1065 *rl = alloc_whole_rl(get_type(expr));
1066 return 1;
1069 int get_absolute_rl(struct expression *expr, struct range_list **rl)
1071 int recurse_cnt = 0;
1073 *rl = _get_rl(expr, RL_ABSOLUTE, &recurse_cnt);
1074 if (!*rl)
1075 *rl = alloc_whole_rl(get_type(expr));
1076 return 1;
1079 int get_real_absolute_rl(struct expression *expr, struct range_list **rl)
1081 int recurse_cnt = 0;
1083 *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1084 if (!*rl)
1085 *rl = alloc_whole_rl(get_type(expr));
1086 return 1;
1089 int custom_get_absolute_rl(struct expression *expr,
1090 struct range_list *(*fn)(struct expression *expr),
1091 struct range_list **rl)
1093 int recurse_cnt = 0;
1095 *rl = NULL;
1096 custom_handle_variable = fn;
1097 *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1098 custom_handle_variable = NULL;
1099 return 1;
1102 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
1104 struct smatch_state *state;
1106 state = get_state(SMATCH_EXTRA, var, sym);
1107 *rl = estate_rl(state);
1108 if (*rl)
1109 return 1;
1110 return 0;
1113 int get_hard_max(struct expression *expr, sval_t *sval)
1115 struct range_list *rl;
1116 int recurse_cnt = 0;
1118 rl = _get_rl(expr, RL_HARD, &recurse_cnt);
1119 if (!rl)
1120 return 0;
1121 *sval = rl_max(rl);
1122 return 1;
1125 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1127 struct range_list *rl;
1128 sval_t tmp;
1129 int recurse_cnt = 0;
1131 rl = _get_rl(expr, RL_FUZZY, &recurse_cnt);
1132 if (!rl)
1133 return 0;
1134 tmp = rl_min(rl);
1135 if (sval_is_negative(tmp) && sval_is_min(tmp))
1136 return 0;
1137 *sval = tmp;
1138 return 1;
1141 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1143 struct range_list *rl;
1144 sval_t max;
1145 int recurse_cnt = 0;
1147 rl = _get_rl(expr, RL_FUZZY, &recurse_cnt);
1148 if (!rl)
1149 return 0;
1150 max = rl_max(rl);
1151 if (max.uvalue > INT_MAX - 10000)
1152 return 0;
1153 *sval = max;
1154 return 1;
1157 int get_absolute_min(struct expression *expr, sval_t *sval)
1159 struct range_list *rl;
1160 struct symbol *type;
1161 int recurse_cnt = 0;
1163 type = get_type(expr);
1164 if (!type)
1165 type = &llong_ctype; // FIXME: this is wrong but places assume get type can't fail.
1166 rl = _get_rl(expr, RL_ABSOLUTE, &recurse_cnt);
1167 if (rl)
1168 *sval = rl_min(rl);
1169 else
1170 *sval = sval_type_min(type);
1172 if (sval_cmp(*sval, sval_type_min(type)) < 0)
1173 *sval = sval_type_min(type);
1174 return 1;
1177 int get_absolute_max(struct expression *expr, sval_t *sval)
1179 struct range_list *rl;
1180 struct symbol *type;
1181 int recurse_cnt = 0;
1183 type = get_type(expr);
1184 if (!type)
1185 type = &llong_ctype;
1186 rl = _get_rl(expr, RL_ABSOLUTE, &recurse_cnt);
1187 if (rl)
1188 *sval = rl_max(rl);
1189 else
1190 *sval = sval_type_max(type);
1192 if (sval_cmp(sval_type_max(type), *sval) < 0)
1193 *sval = sval_type_max(type);
1194 return 1;
1197 int known_condition_true(struct expression *expr)
1199 sval_t tmp;
1201 if (!expr)
1202 return 0;
1204 if (get_value(expr, &tmp) && tmp.value)
1205 return 1;
1207 return 0;
1210 int known_condition_false(struct expression *expr)
1212 if (!expr)
1213 return 0;
1215 if (is_zero(expr))
1216 return 1;
1218 if (expr->type == EXPR_CALL) {
1219 if (sym_name_is("__builtin_constant_p", expr->fn))
1220 return 1;
1222 return 0;
1225 int implied_condition_true(struct expression *expr)
1227 sval_t tmp;
1229 if (!expr)
1230 return 0;
1232 if (known_condition_true(expr))
1233 return 1;
1234 if (get_implied_value(expr, &tmp) && tmp.value)
1235 return 1;
1237 if (expr->type == EXPR_POSTOP)
1238 return implied_condition_true(expr->unop);
1240 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1241 return implied_not_equal(expr->unop, 1);
1242 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1243 return implied_not_equal(expr->unop, -1);
1245 expr = strip_expr(expr);
1246 switch (expr->type) {
1247 case EXPR_COMPARE:
1248 if (do_comparison(expr) == 1)
1249 return 1;
1250 break;
1251 case EXPR_PREOP:
1252 if (expr->op == '!') {
1253 if (implied_condition_false(expr->unop))
1254 return 1;
1255 break;
1257 break;
1258 default:
1259 if (implied_not_equal(expr, 0) == 1)
1260 return 1;
1261 break;
1263 return 0;
1266 int implied_condition_false(struct expression *expr)
1268 struct expression *tmp;
1269 sval_t sval;
1271 if (!expr)
1272 return 0;
1274 if (known_condition_false(expr))
1275 return 1;
1277 switch (expr->type) {
1278 case EXPR_COMPARE:
1279 if (do_comparison(expr) == 2)
1280 return 1;
1281 case EXPR_PREOP:
1282 if (expr->op == '!') {
1283 if (implied_condition_true(expr->unop))
1284 return 1;
1285 break;
1287 tmp = strip_expr(expr);
1288 if (tmp != expr)
1289 return implied_condition_false(tmp);
1290 break;
1291 default:
1292 if (get_implied_value(expr, &sval) && sval.value == 0)
1293 return 1;
1294 break;
1296 return 0;
1299 int can_integer_overflow(struct symbol *type, struct expression *expr)
1301 int op;
1302 sval_t lmax, rmax, res;
1304 if (!type)
1305 type = &int_ctype;
1307 expr = strip_expr(expr);
1309 if (expr->type == EXPR_ASSIGNMENT) {
1310 switch(expr->op) {
1311 case SPECIAL_MUL_ASSIGN:
1312 op = '*';
1313 break;
1314 case SPECIAL_ADD_ASSIGN:
1315 op = '+';
1316 break;
1317 case SPECIAL_SHL_ASSIGN:
1318 op = SPECIAL_LEFTSHIFT;
1319 break;
1320 default:
1321 return 0;
1323 } else if (expr->type == EXPR_BINOP) {
1324 if (expr->op != '*' && expr->op != '+' && expr->op != SPECIAL_LEFTSHIFT)
1325 return 0;
1326 op = expr->op;
1327 } else {
1328 return 0;
1331 get_absolute_max(expr->left, &lmax);
1332 get_absolute_max(expr->right, &rmax);
1334 if (sval_binop_overflows(lmax, op, rmax))
1335 return 1;
1337 res = sval_binop(lmax, op, rmax);
1338 if (sval_cmp(res, sval_type_max(type)) > 0)
1339 return 1;
1340 return 0;