15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 */
17
18 /*
19 * The point here is to store the relationships between two variables.
20 * Ie: y > x.
21 * To do that we create a state with the two variables in alphabetical order:
22 * ->name = "x vs y" and the state would be "<". On the false path the state
23 * would be ">=".
24 *
25 * Part of the trick of it is that if x or y is modified then we need to reset
26 * the state. We need to keep a list of all the states which depend on x and
27 * all the states which depend on y. The link_id code handles this.
28 *
29 */
30
31 #include "smatch.h"
32 #include "smatch_extra.h"
33 #include "smatch_slist.h"
34
35 static int compare_id;
36 static int link_id;
37 static int inc_dec_id;
38 static int inc_dec_link_id;
39
40 static void add_comparison(struct expression *left, int comparison, struct expression *right);
41
42 /* for handling for loops */
43 STATE(start);
44 STATE(incremented);
45
46 ALLOCATOR(compare_data, "compare data");
47
48 static struct symbol *vsl_to_sym(struct var_sym_list *vsl)
49 {
50 struct var_sym *vs;
51
52 if (!vsl)
53 return NULL;
54 if (ptr_list_size((struct ptr_list *)vsl) != 1)
55 return NULL;
525 if (GT && LT)
526 return IMPOSSIBLE_COMPARISON;
527 if (GT && NE)
528 return '>';
529 if (LT && NE)
530 return '<';
531 if (NE == 2)
532 return SPECIAL_NOTEQUAL;
533 if (total == 2 && (LT || GT) && EQ)
534 return IMPOSSIBLE_COMPARISON;
535
536 return UNKNOWN_COMPARISON;
537 }
538
539 static void pre_merge_hook(struct sm_state *cur, struct sm_state *other)
540 {
541 struct compare_data *data = cur->state->data;
542 int extra, new;
543 static bool in_recurse;
544
545 if (!data)
546 return;
547
548 if (in_recurse)
549 return;
550 in_recurse = true;
551 extra = comparison_from_extra(data->left, data->right);
552 in_recurse = false;
553 if (!extra)
554 return;
555 new = comparison_intersection(extra, data->comparison);
556 if (new == data->comparison)
557 return;
558
559 set_state(compare_id, cur->name, NULL,
560 alloc_compare_state(data->left, data->left_var, data->left_vsl,
561 new,
562 data->right, data->right_var, data->right_vsl));
563 }
564
565 struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
566 {
567 struct compare_data *data = s1->data;
568 int op;
569
570 if (!data)
571 return &undefined;
572
573 op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
574 return alloc_compare_state(
575 data->left, data->left_var, data->left_vsl,
576 op,
577 data->right, data->right_var, data->right_vsl);
578 }
579
607 char orig[64];
608 char state_name[128];
609 struct smatch_state *state;
610 struct string_list *links;
611 char *link;
612
613 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
614 struct var_sym_list *left_vsl = NULL;
615 struct var_sym_list *right_vsl = NULL;
616
617 if (!param->ident)
618 continue;
619 snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
620 snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
621 add_var_sym(&left_vsl, param->ident->name, param);
622 add_var_sym(&right_vsl, orig, param);
623 state = alloc_compare_state(
624 NULL, param->ident->name, left_vsl,
625 SPECIAL_EQUAL,
626 NULL, alloc_sname(orig), right_vsl);
627 set_state(compare_id, state_name, NULL, state);
628
629 link = alloc_sname(state_name);
630 links = NULL;
631 insert_string(&links, link);
632 state = alloc_link_state(links);
633 set_state(link_id, param->ident->name, param, state);
634 } END_FOR_EACH_PTR(param);
635 }
636
637 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
638 {
639 struct smatch_state *ret;
640 struct string_list *links;
641
642 links = combine_string_lists(s1->data, s2->data);
643 ret = alloc_link_state(links);
644 return ret;
645 }
646
647 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
658
659 new = alloc_sname(link);
660 insert_string(&links, new);
661
662 new_state = alloc_link_state(links);
663 set_state(link_id, var, sym, new_state);
664 }
665
666 static void match_inc(struct sm_state *sm, bool preserve)
667 {
668 struct string_list *links;
669 struct smatch_state *state, *new;
670 struct compare_data *data;
671 char *tmp;
672 int flip;
673 int op;
674
675 links = sm->state->data;
676
677 FOR_EACH_PTR(links, tmp) {
678 state = get_state(compare_id, tmp, NULL);
679 if (!state)
680 continue;
681 data = state->data;
682 if (!data)
683 continue;
684
685 flip = 0;
686 if (strncmp(sm->name, tmp, strlen(sm->name)) != 0 ||
687 tmp[strlen(sm->name)] != ' ')
688 flip = 1;
689
690 op = state_to_comparison(state);
691
692 switch (flip ? flip_comparison(op) : op) {
693 case SPECIAL_EQUAL:
694 case SPECIAL_GTE:
695 case SPECIAL_UNSIGNED_GTE:
696 case '>':
697 case SPECIAL_UNSIGNED_GT:
698 if (preserve)
699 break;
700 new = alloc_compare_state(
701 data->left, data->left_var, data->left_vsl,
702 flip ? '<' : '>',
703 data->right, data->right_var, data->right_vsl);
704 set_state(compare_id, tmp, NULL, new);
705 break;
706 case '<':
707 case SPECIAL_UNSIGNED_LT:
708 new = alloc_compare_state(
709 data->left, data->left_var, data->left_vsl,
710 flip ? SPECIAL_GTE : SPECIAL_LTE,
711 data->right, data->right_var, data->right_vsl);
712 set_state(compare_id, tmp, NULL, new);
713 break;
714 default:
715 new = alloc_compare_state(
716 data->left, data->left_var, data->left_vsl,
717 UNKNOWN_COMPARISON,
718 data->right, data->right_var, data->right_vsl);
719 set_state(compare_id, tmp, NULL, new);
720 }
721 } END_FOR_EACH_PTR(tmp);
722 }
723
724 static void match_dec(struct sm_state *sm, bool preserve)
725 {
726 struct string_list *links;
727 struct smatch_state *state;
728 char *tmp;
729
730 links = sm->state->data;
731
732 FOR_EACH_PTR(links, tmp) {
733 struct compare_data *data;
734 struct smatch_state *new;
735
736 state = get_state(compare_id, tmp, NULL);
737 if (!state || !state->data)
738 continue;
739
740 data = state->data;
741
742 switch (state_to_comparison(state)) {
743 case SPECIAL_EQUAL:
744 case SPECIAL_LTE:
745 case SPECIAL_UNSIGNED_LTE:
746 case '<':
747 case SPECIAL_UNSIGNED_LT: {
748 if (preserve)
749 break;
750
751 new = alloc_compare_state(
752 data->left, data->left_var, data->left_vsl,
753 '<',
754 data->right, data->right_var, data->right_vsl);
755 set_state(compare_id, tmp, NULL, new);
756 break;
757 }
758 default:
759 new = alloc_compare_state(
760 data->left, data->left_var, data->left_vsl,
761 UNKNOWN_COMPARISON,
762 data->right, data->right_var, data->right_vsl);
763 set_state(compare_id, tmp, NULL, new);
764 }
765 } END_FOR_EACH_PTR(tmp);
766 }
767
768 static void reset_sm(struct sm_state *sm)
769 {
770 struct string_list *links;
771 char *tmp;
772
773 links = sm->state->data;
774
775 FOR_EACH_PTR(links, tmp) {
776 struct smatch_state *old, *new;
777
778 old = get_state(compare_id, tmp, NULL);
779 if (!old || !old->data) {
780 new = &undefined;
781 } else {
782 struct compare_data *data = old->data;
783
784 new = alloc_compare_state(
785 data->left, data->left_var, data->left_vsl,
786 UNKNOWN_COMPARISON,
787 data->right, data->right_var, data->right_vsl);
788 }
789 set_state(compare_id, tmp, NULL, new);
790 } END_FOR_EACH_PTR(tmp);
791 set_state(link_id, sm->name, sm->sym, &undefined);
792 }
793
794 static bool match_add_sub_assign(struct sm_state *sm, struct expression *expr)
795 {
796 struct range_list *rl;
797 sval_t zero = { .type = &int_ctype };
798
799 if (!expr || expr->type != EXPR_ASSIGNMENT)
800 return false;
801 if (expr->op != SPECIAL_ADD_ASSIGN && expr->op != SPECIAL_SUB_ASSIGN)
802 return false;
803
804 get_absolute_rl(expr->right, &rl);
805 if (sval_is_negative(rl_min(rl))) {
806 reset_sm(sm);
807 return false;
808 }
809
971 save_link_var_sym(var, sym, link);
972 free_string(var);
973 }
974
975 static int get_orig_comparison(struct stree *pre_stree, const char *left, const char *right)
976 {
977 struct smatch_state *state;
978 struct compare_data *data;
979 int flip = 0;
980 char state_name[256];
981
982 if (strcmp(left, right) > 0) {
983 const char *tmp = right;
984
985 flip = 1;
986 right = left;
987 left = tmp;
988 }
989
990 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
991 state = get_state_stree(pre_stree, compare_id, state_name, NULL);
992 if (!state || !state->data)
993 return 0;
994 data = state->data;
995 if (flip)
996 return flip_comparison(data->comparison);
997 return data->comparison;
998
999 }
1000
1001 static int have_common_var_sym(struct var_sym_list *left_vsl, struct var_sym_list *right_vsl)
1002 {
1003 struct var_sym *tmp;
1004
1005 FOR_EACH_PTR(left_vsl, tmp) {
1006 if (in_var_sym_list(right_vsl, tmp->var, tmp->sym))
1007 return 1;
1008 } END_FOR_EACH_PTR(tmp);
1009
1010 return 0;
1011 }
1024 const char *left_var, struct var_sym_list *left_vsl,
1025 int left_comparison, int left_false_comparison,
1026 const char *mid_var, struct var_sym_list *mid_vsl,
1027 struct string_list *links)
1028 {
1029 struct smatch_state *state;
1030 struct smatch_state *true_state, *false_state;
1031 struct compare_data *data;
1032 struct expression *right_expr;
1033 const char *right_var;
1034 struct var_sym_list *right_vsl;
1035 int orig_comparison;
1036 int right_comparison;
1037 int true_comparison;
1038 int false_comparison;
1039 char *tmp;
1040 char state_name[256];
1041 struct var_sym *vs;
1042
1043 FOR_EACH_PTR(links, tmp) {
1044 state = get_state_stree(pre_stree, compare_id, tmp, NULL);
1045 if (!state || !state->data)
1046 continue;
1047 data = state->data;
1048 right_comparison = data->comparison;
1049 right_expr = data->right;
1050 right_var = data->right_var;
1051 right_vsl = data->right_vsl;
1052 if (strcmp(mid_var, right_var) == 0) {
1053 right_expr = data->left;
1054 right_var = data->left_var;
1055 right_vsl = data->left_vsl;
1056 right_comparison = flip_comparison(right_comparison);
1057 }
1058 if (have_common_var_sym(left_vsl, right_vsl))
1059 continue;
1060
1061 orig_comparison = get_orig_comparison(pre_stree, left_var, right_var);
1062
1063 true_comparison = combine_comparisons(left_comparison, right_comparison);
1064 false_comparison = combine_comparisons(left_false_comparison, right_comparison);
1083
1084 if (!true_comparison && !false_comparison)
1085 continue;
1086
1087 if (true_comparison)
1088 true_state = alloc_compare_state(
1089 left_expr, left_var, left_vsl,
1090 true_comparison,
1091 right_expr, right_var, right_vsl);
1092 else
1093 true_state = NULL;
1094 if (false_comparison)
1095 false_state = alloc_compare_state(
1096 left_expr, left_var, left_vsl,
1097 false_comparison,
1098 right_expr, right_var, right_vsl);
1099 else
1100 false_state = NULL;
1101
1102 snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var);
1103 set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
1104 FOR_EACH_PTR(left_vsl, vs) {
1105 save_link_var_sym(vs->var, vs->sym, state_name);
1106 } END_FOR_EACH_PTR(vs);
1107 FOR_EACH_PTR(right_vsl, vs) {
1108 save_link_var_sym(vs->var, vs->sym, state_name);
1109 } END_FOR_EACH_PTR(vs);
1110 if (!vsl_to_sym(left_vsl))
1111 save_link_var_sym(left_var, NULL, state_name);
1112 if (!vsl_to_sym(right_vsl))
1113 save_link_var_sym(right_var, NULL, state_name);
1114 } END_FOR_EACH_PTR(tmp);
1115 }
1116
1117 static void update_tf_data(struct stree *pre_stree,
1118 struct expression *left_expr,
1119 const char *left_name, struct var_sym_list *left_vsl,
1120 struct expression *right_expr,
1121 const char *right_name, struct var_sym_list *right_vsl,
1122 int true_comparison, int false_comparison)
1123 {
1182 store_link(inc_dec_link_id, cap_name, cap_sym, iter_name, iter_sym);
1183
1184 free_string(iter_name);
1185 free_string(cap_name);
1186 return;
1187 }
1188
1189 /* Second time checking the condtion */
1190 if (__prev_stmt != __cur_stmt->iterator_post_statement)
1191 return;
1192
1193 if (get_state_chunk(inc_dec_id, expr->left) != &incremented)
1194 return;
1195
1196 data = false_state->data;
1197 false_state = alloc_compare_state(
1198 data->left, data->left_var, data->left_vsl,
1199 SPECIAL_EQUAL,
1200 data->right, data->right_var, data->right_vsl);
1201
1202 set_true_false_states(compare_id, state_name, NULL, NULL, false_state);
1203 }
1204
1205 static int is_plus_one(struct expression *expr)
1206 {
1207 sval_t sval;
1208
1209 if (expr->type != EXPR_BINOP || expr->op != '+')
1210 return 0;
1211 if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1212 return 0;
1213 return 1;
1214 }
1215
1216 static int is_minus_one(struct expression *expr)
1217 {
1218 sval_t sval;
1219
1220 if (expr->type != EXPR_BINOP || expr->op != '-')
1221 return 0;
1222 if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1323 }
1324
1325 orig_comparison = get_comparison(left_expr, right_expr);
1326 op = comparison_intersection(orig_comparison, op);
1327 false_op = comparison_intersection(orig_comparison, false_op);
1328
1329 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
1330 true_state = alloc_compare_state(
1331 left_expr, left, left_vsl,
1332 op,
1333 right_expr, right, right_vsl);
1334 false_state = alloc_compare_state(
1335 left_expr, left, left_vsl,
1336 false_op,
1337 right_expr, right, right_vsl);
1338
1339 pre_stree = clone_stree(__get_cur_stree());
1340 update_tf_data(pre_stree, left_expr, left, left_vsl, right_expr, right, right_vsl, op, false_op);
1341 free_stree(&pre_stree);
1342
1343 set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
1344 __compare_param_limit_hook(left_expr, right_expr, state_name, true_state, false_state);
1345 save_link(left_expr, state_name);
1346 save_link(right_expr, state_name);
1347
1348 if (_false_state)
1349 *_false_state = false_state;
1350 if (_state_name)
1351 *_state_name = state_name;
1352 free:
1353 free_string(left);
1354 free_string(right);
1355 }
1356
1357 void __comparison_match_condition(struct expression *expr)
1358 {
1359 struct expression *left, *right, *new_left, *new_right, *tmp;
1360 struct smatch_state *false_state = NULL;
1361 char *state_name = NULL;
1362 int redo, count;
1363
1425
1426 if (strcmp(left_name, right_name) > 0) {
1427 struct expression *tmp_expr = left_expr;
1428 const char *tmp_name = left_name;
1429 struct var_sym_list *tmp_vsl = left_vsl;
1430
1431 left_expr = right_expr;
1432 left_name = right_name;
1433 left_vsl = right_vsl;
1434 right_expr = tmp_expr;
1435 right_name = tmp_name;
1436 right_vsl = tmp_vsl;
1437 comparison = flip_comparison(comparison);
1438 }
1439 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1440 state = alloc_compare_state(
1441 left_expr, left_name, left_vsl,
1442 comparison,
1443 right_expr, right_name, right_vsl);
1444
1445 set_state(compare_id, state_name, NULL, state);
1446
1447 FOR_EACH_PTR(left_vsl, vs) {
1448 save_link_var_sym(vs->var, vs->sym, state_name);
1449 } END_FOR_EACH_PTR(vs);
1450 FOR_EACH_PTR(right_vsl, vs) {
1451 save_link_var_sym(vs->var, vs->sym, state_name);
1452 } END_FOR_EACH_PTR(vs);
1453 }
1454
1455 static void add_comparison(struct expression *left, int comparison, struct expression *right)
1456 {
1457 char *left_name = NULL;
1458 char *right_name = NULL;
1459 struct symbol *left_sym, *right_sym;
1460 struct var_sym_list *left_vsl, *right_vsl;
1461 struct smatch_state *state;
1462 char state_name[256];
1463
1464 left_name = chunk_to_var_sym(left, &left_sym);
1465 if (!left_name)
1475 struct symbol *tmp_sym = left_sym;
1476 char *tmp_name = left_name;
1477 struct var_sym_list *tmp_vsl = left_vsl;
1478
1479 left = right;
1480 left_name = right_name;
1481 left_sym = right_sym;
1482 left_vsl = right_vsl;
1483 right = tmp_expr;
1484 right_name = tmp_name;
1485 right_sym = tmp_sym;
1486 right_vsl = tmp_vsl;
1487 comparison = flip_comparison(comparison);
1488 }
1489 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1490 state = alloc_compare_state(
1491 left, left_name, left_vsl,
1492 comparison,
1493 right, right_name, right_vsl);
1494
1495 set_state(compare_id, state_name, NULL, state);
1496 save_link(left, state_name);
1497 save_link(right, state_name);
1498
1499 free:
1500 free_string(left_name);
1501 free_string(right_name);
1502 }
1503
1504 static void match_assign_add(struct expression *expr)
1505 {
1506 struct expression *right;
1507 struct expression *r_left, *r_right;
1508 sval_t left_tmp, right_tmp;
1509
1510 right = strip_expr(expr->right);
1511 r_left = strip_expr(right->left);
1512 r_right = strip_expr(right->right);
1513
1514 get_absolute_min(r_left, &left_tmp);
1515 get_absolute_min(r_right, &right_tmp);
1592 struct expression *expr;
1593 const char *var;
1594 struct var_sym_list *vsl;
1595 int comparison;
1596 char *tmp;
1597
1598 left_var = chunk_to_var_sym(left, &left_sym);
1599 if (!left_var)
1600 goto done;
1601 left_vsl = expr_to_vsl(left);
1602 right_var = chunk_to_var_sym(right, &right_sym);
1603 if (!right_var)
1604 goto done;
1605
1606 state = get_state(link_id, right_var, right_sym);
1607 if (!state)
1608 return;
1609 links = state->data;
1610
1611 FOR_EACH_PTR(links, tmp) {
1612 state = get_state(compare_id, tmp, NULL);
1613 if (!state || !state->data)
1614 continue;
1615 data = state->data;
1616 comparison = data->comparison;
1617 expr = data->right;
1618 var = data->right_var;
1619 vsl = data->right_vsl;
1620 if (strcmp(var, right_var) == 0) {
1621 expr = data->left;
1622 var = data->left_var;
1623 vsl = data->left_vsl;
1624 comparison = flip_comparison(comparison);
1625 }
1626 /* n = copy_from_user(dest, src, n); leads to n <= n which is nonsense */
1627 if (strcmp(left_var, var) == 0)
1628 continue;
1629 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1630 } END_FOR_EACH_PTR(tmp);
1631
1632 done:
1661 char buf[256];
1662 struct smatch_state *state;
1663 int invert = 0;
1664 int ret = 0;
1665
1666 if (!one || !two)
1667 return UNKNOWN_COMPARISON;
1668
1669 if (strcmp(one, two) == 0)
1670 return SPECIAL_EQUAL;
1671
1672 if (strcmp(one, two) > 0) {
1673 const char *tmp = one;
1674
1675 one = two;
1676 two = tmp;
1677 invert = 1;
1678 }
1679
1680 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1681 state = get_state(compare_id, buf, NULL);
1682 if (state)
1683 ret = state_to_comparison(state);
1684
1685 if (invert)
1686 ret = flip_comparison(ret);
1687
1688 return ret;
1689 }
1690
1691 static int get_comparison_helper(struct expression *a, struct expression *b, bool use_extra)
1692 {
1693 char *one = NULL;
1694 char *two = NULL;
1695 int ret = UNKNOWN_COMPARISON;
1696 int extra = UNKNOWN_COMPARISON;
1697
1698 if (a == UNKNOWN_COMPARISON ||
1699 b == UNKNOWN_COMPARISON)
1700 return UNKNOWN_COMPARISON;
1701
1767 goto free;
1768 two = chunk_to_var(b);
1769 if (!two)
1770 goto free;
1771
1772
1773 if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
1774 ret = 1;
1775 goto free;
1776 }
1777
1778 if (strcmp(one, two) > 0) {
1779 char *tmp = one;
1780
1781 one = two;
1782 two = tmp;
1783 comparison = flip_comparison(comparison);
1784 }
1785
1786 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1787 sm = get_sm_state(compare_id, buf, NULL);
1788 if (!sm)
1789 goto free;
1790
1791 FOR_EACH_PTR(sm->possible, sm) {
1792 if (!sm->state->data)
1793 continue;
1794 saved = ((struct compare_data *)sm->state->data)->comparison;
1795 if (saved == comparison)
1796 ret = 1;
1797 if (comparison == SPECIAL_EQUAL &&
1798 (saved == SPECIAL_LTE ||
1799 saved == SPECIAL_GTE ||
1800 saved == SPECIAL_UNSIGNED_LTE ||
1801 saved == SPECIAL_UNSIGNED_GTE))
1802 ret = 1;
1803 if (ret == 1)
1804 goto free;
1805 } END_FOR_EACH_PTR(sm);
1806
1807 return ret;
1808 free:
1809 free_string(one);
1810 free_string(two);
1811 return ret;
1812 }
1813
1814 struct state_list *get_all_comparisons(struct expression *expr)
1815 {
1816 struct smatch_state *state;
1817 struct string_list *links;
1818 struct state_list *ret = NULL;
1819 struct sm_state *sm;
1820 char *tmp;
1821
1822 state = get_state_chunk(link_id, expr);
1823 if (!state)
1824 return NULL;
1825 links = state->data;
1826
1827 FOR_EACH_PTR(links, tmp) {
1828 sm = get_sm_state(compare_id, tmp, NULL);
1829 if (!sm)
1830 continue;
1831 // FIXME have to compare name with vsl
1832 add_ptr_list(&ret, sm);
1833 } END_FOR_EACH_PTR(tmp);
1834
1835 return ret;
1836 }
1837
1838 struct state_list *get_all_possible_equal_comparisons(struct expression *expr)
1839 {
1840 struct smatch_state *state;
1841 struct string_list *links;
1842 struct state_list *ret = NULL;
1843 struct sm_state *sm;
1844 char *tmp;
1845
1846 state = get_state_chunk(link_id, expr);
1847 if (!state)
1848 return NULL;
1849 links = state->data;
1850
1851 FOR_EACH_PTR(links, tmp) {
1852 sm = get_sm_state(compare_id, tmp, NULL);
1853 if (!sm)
1854 continue;
1855 if (!strchr(sm->state->name, '='))
1856 continue;
1857 if (strcmp(sm->state->name, "!=") == 0)
1858 continue;
1859 add_ptr_list(&ret, sm);
1860 } END_FOR_EACH_PTR(tmp);
1861
1862 return ret;
1863 }
1864
1865 struct state_list *get_all_possible_not_equal_comparisons(struct expression *expr)
1866 {
1867 struct smatch_state *state;
1868 struct string_list *links;
1869 struct state_list *ret = NULL;
1870 struct sm_state *sm;
1871 struct sm_state *possible;
1872 char *link;
1873
1874 return NULL;
1875
1876 state = get_state_chunk(link_id, expr);
1877 if (!state)
1878 return NULL;
1879 links = state->data;
1880
1881 FOR_EACH_PTR(links, link) {
1882 sm = get_sm_state(compare_id, link, NULL);
1883 if (!sm)
1884 continue;
1885 FOR_EACH_PTR(sm->possible, possible) {
1886 if (strcmp(possible->state->name, "!=") != 0)
1887 continue;
1888 add_ptr_list(&ret, sm);
1889 break;
1890 } END_FOR_EACH_PTR(link);
1891 } END_FOR_EACH_PTR(link);
1892
1893 return ret;
1894 }
1895
1896 static void update_links_from_call(struct expression *left,
1897 int left_compare,
1898 struct expression *right)
1899 {
1900 struct string_list *links;
1901 struct smatch_state *state;
1902 struct compare_data *data;
1907 struct expression *expr;
1908 const char *var;
1909 struct var_sym_list *vsl;
1910 int comparison;
1911 char *tmp;
1912
1913 left_var = chunk_to_var_sym(left, &left_sym);
1914 if (!left_var)
1915 goto done;
1916 left_vsl = expr_to_vsl(left);
1917 right_var = chunk_to_var_sym(right, &right_sym);
1918 if (!right_var)
1919 goto done;
1920
1921 state = get_state(link_id, right_var, right_sym);
1922 if (!state)
1923 return;
1924 links = state->data;
1925
1926 FOR_EACH_PTR(links, tmp) {
1927 state = get_state(compare_id, tmp, NULL);
1928 if (!state || !state->data)
1929 continue;
1930 data = state->data;
1931 comparison = data->comparison;
1932 expr = data->right;
1933 var = data->right_var;
1934 vsl = data->right_vsl;
1935 if (strcmp(var, right_var) == 0) {
1936 expr = data->left;
1937 var = data->left_var;
1938 vsl = data->left_vsl;
1939 comparison = flip_comparison(comparison);
1940 }
1941 comparison = combine_comparisons(left_compare, comparison);
1942 if (!comparison)
1943 continue;
1944 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1945 } END_FOR_EACH_PTR(tmp);
1946
1947 done:
2156 char *link;
2157 char info_buf[256];
2158 int i;
2159
2160 i = -1;
2161 FOR_EACH_PTR(expr->args, arg) {
2162 i++;
2163
2164 state = get_state_chunk(link_id, arg);
2165 if (!state)
2166 continue;
2167
2168 links = state->data;
2169 FOR_EACH_PTR(links, link) {
2170 struct var_sym_list *right_vsl;
2171 struct var_sym *right_vs;
2172
2173
2174 if (strstr(link, " orig"))
2175 continue;
2176 sm = get_sm_state(compare_id, link, NULL);
2177 if (!sm)
2178 continue;
2179 data = sm->state->data;
2180 if (!data ||
2181 data->comparison == UNKNOWN_COMPARISON ||
2182 data->comparison == IMPOSSIBLE_COMPARISON)
2183 continue;
2184 arg_name = expr_to_var(arg);
2185 if (!arg_name)
2186 continue;
2187
2188 right_vsl = NULL;
2189 if (strcmp(data->left_var, arg_name) == 0) {
2190 comparison = data->comparison;
2191 right_name = data->right_var;
2192 right_vsl = data->right_vsl;
2193 } else if (strcmp(data->right_var, arg_name) == 0) {
2194 comparison = flip_comparison(data->comparison);
2195 right_name = data->left_var;
2196 right_vsl = data->left_vsl;
2211 free_string(arg_name);
2212 } END_FOR_EACH_PTR(link);
2213 } END_FOR_EACH_PTR(arg);
2214 }
2215
2216 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *link_sm)
2217 {
2218 struct sm_state *compare_sm;
2219 struct string_list *links;
2220 char *link;
2221 struct compare_data *data;
2222 struct var_sym *left, *right;
2223 static char info_buf[256];
2224 const char *right_name;
2225
2226 if (strstr(printed_name, " orig"))
2227 return;
2228
2229 links = link_sm->state->data;
2230 FOR_EACH_PTR(links, link) {
2231 compare_sm = get_sm_state(compare_id, link, NULL);
2232 if (!compare_sm)
2233 continue;
2234 data = compare_sm->state->data;
2235 if (!data || !data->comparison)
2236 continue;
2237
2238 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2239 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2240 continue;
2241 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2242 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2243 if (left->sym == right->sym &&
2244 strcmp(left->var, right->var) == 0)
2245 continue;
2246 /*
2247 * Both parameters link to this comparison so only
2248 * record the first one.
2249 */
2250 if (left->sym != link_sm->sym ||
2251 strcmp(left->var, link_sm->name) != 0)
2304 {
2305 struct sm_state *tmp;
2306 struct string_list *links;
2307 char *link;
2308 struct sm_state *sm;
2309 struct compare_data *data;
2310 struct var_sym *left, *right;
2311 int left_param, right_param;
2312 char left_buf[256];
2313 char right_buf[256];
2314 char info_buf[258];
2315 const char *tmp_name;
2316
2317 print_return_value_comparison(return_id, return_ranges, expr);
2318
2319 FOR_EACH_MY_SM(link_id, __get_cur_stree(), tmp) {
2320 if (get_param_num_from_sym(tmp->sym) < 0)
2321 continue;
2322 links = tmp->state->data;
2323 FOR_EACH_PTR(links, link) {
2324 sm = get_sm_state(compare_id, link, NULL);
2325 if (!sm)
2326 continue;
2327 data = sm->state->data;
2328 if (!data ||
2329 data->comparison == UNKNOWN_COMPARISON ||
2330 data->comparison == IMPOSSIBLE_COMPARISON)
2331 continue;
2332 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2333 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2334 continue;
2335 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2336 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2337 if (left->sym == right->sym &&
2338 strcmp(left->var, right->var) == 0)
2339 continue;
2340 /*
2341 * Both parameters link to this comparison so only
2342 * record the first one.
2343 */
2344 if (left->sym != tmp->sym ||
2522 if (expr->type != EXPR_CALL)
2523 return 0;
2524
2525 if (!split_op_param_key(value, &op, &right_param, &right_key))
2526 return 0;
2527
2528 left_arg = get_argument_from_call_expr(expr->args, left_param);
2529 if (!left_arg)
2530 return 0;
2531
2532 right_arg = get_argument_from_call_expr(expr->args, right_param);
2533 if (!right_arg)
2534 return 0;
2535
2536 left_name = get_variable_from_key(left_arg, left_key, &left_sym);
2537 right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2538 if (!left_name || !right_name)
2539 goto free;
2540
2541 snprintf(buf, sizeof(buf), "%s vs %s", left_name, right_name);
2542 state = get_state(compare_id, buf, NULL);
2543 if (!state)
2544 goto free;
2545 state_op = state_to_comparison(state);
2546 if (!state_op)
2547 goto free;
2548
2549 if (!comparison_intersection(remove_unsigned_from_comparison(state_op), op))
2550 ret = 1;
2551 free:
2552 free_string(left_name);
2553 free_string(right_name);
2554 return ret;
2555 }
2556
2557 int impossibly_high_comparison(struct expression *expr)
2558 {
2559 struct smatch_state *link_state;
2560 struct sm_state *sm;
2561 struct string_list *links;
2562 char *link;
2563 struct compare_data *data;
2564
2565 link_state = get_state_expr(link_id, expr);
2566 if (!link_state) {
2567 if (expr->type == EXPR_BINOP &&
2568 (impossibly_high_comparison(expr->left) ||
2569 impossibly_high_comparison(expr->right)))
2570 return 1;
2571 return 0;
2572 }
2573
2574 links = link_state->data;
2575 FOR_EACH_PTR(links, link) {
2576 sm = get_sm_state(compare_id, link, NULL);
2577 if (!sm)
2578 continue;
2579 data = sm->state->data;
2580 if (!data)
2581 continue;
2582 if (!possibly_true(data->left, data->comparison, data->right))
2583 return 1;
2584 } END_FOR_EACH_PTR(link);
2585
2586 return 0;
2587 }
2588
2589 static void free_data(struct symbol *sym)
2590 {
2591 if (__inline_fn)
2592 return;
2593 clear_compare_data_alloc();
2594 }
2595
2596 void register_comparison(int id)
2597 {
2598 compare_id = id;
2599 set_dynamic_states(compare_id);
2600 add_hook(&save_start_states, AFTER_DEF_HOOK);
2601 add_unmatched_state_hook(compare_id, unmatched_comparison);
2602 add_pre_merge_hook(compare_id, &pre_merge_hook);
2603 add_merge_hook(compare_id, &merge_compare_states);
2604 add_hook(&free_data, AFTER_FUNC_HOOK);
2605 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2606 add_split_return_callback(&print_return_comparison);
2607
2608 select_return_states_hook(PARAM_COMPARE, &db_return_comparison);
2609 add_hook(&match_preop, OP_HOOK);
2610 }
2611
2612 void register_comparison_late(int id)
2613 {
2614 add_hook(&match_assign, ASSIGNMENT_HOOK);
2615 }
2616
2617 void register_comparison_links(int id)
2618 {
2619 link_id = id;
2620 db_ignore_states(link_id);
2621 set_dynamic_states(link_id);
2622 add_merge_hook(link_id, &merge_links);
2623 add_modification_hook(link_id, &match_modify);
2624 add_modification_hook_late(link_id, match_inc_dec);
2625
2626 add_member_info_callback(link_id, struct_member_callback);
2627 }
2628
2629 void register_comparison_inc_dec(int id)
2630 {
2631 inc_dec_id = id;
2632 add_modification_hook_late(inc_dec_id, &iter_modify);
2633 }
2634
2635 void register_comparison_inc_dec_links(int id)
2636 {
2637 inc_dec_link_id = id;
2638 set_dynamic_states(inc_dec_link_id);
2639 set_up_link_functions(inc_dec_id, inc_dec_link_id);
2640 }
2641
2642 static void filter_by_sm(struct sm_state *sm, int op,
2643 struct state_list **true_stack,
2644 struct state_list **false_stack)
2645 {
2646 struct compare_data *data;
2647 int is_true = 0;
2648 int is_false = 0;
2649
2650 if (!sm)
2651 return;
2652 data = sm->state->data;
2653 if (!data || data->comparison == UNKNOWN_COMPARISON)
2654 goto split;
2655 if (data->comparison == IMPOSSIBLE_COMPARISON)
2656 return;
2657
2658 /*
2659 * We want to check that "data->comparison" is totally inside "op". So
2660 * if data->comparison is < and op is <= then that's true. Or if
2661 * data->comparison is == and op is <= then that's true. But if
2662 * data->comparison is <= and op is < than that's neither true nor
2663 * false.
2664 */
2665 if (data->comparison == comparison_intersection(data->comparison, op))
2666 is_true = 1;
2667 if (data->comparison == comparison_intersection(data->comparison, negate_comparison(op)))
2668 is_false = 1;
2669
2670 if (debug_implied()) {
2671 sm_msg("%s: %s: op = '%s' negated '%s'. true_intersect = '%s' false_insersect = '%s' sm = '%s'",
2672 __func__,
2673 sm->state->name,
2674 alloc_sname(show_comparison(op)),
2675 alloc_sname(show_comparison(negate_comparison(op))),
2676 alloc_sname(show_comparison(comparison_intersection(data->comparison, op))),
2677 alloc_sname(show_comparison(comparison_intersection(data->comparison, negate_comparison(op)))),
2678 show_sm(sm));
2679 }
2680
2681 if (is_true)
2682 add_ptr_list(true_stack, sm);
2683 if (is_false)
2684 add_ptr_list(false_stack, sm);
2685 split:
2686 filter_by_sm(sm->left, op, true_stack, false_stack);
2687 filter_by_sm(sm->right, op, true_stack, false_stack);
2688 }
2689
2690 struct sm_state *comparison_implication_hook(struct expression *expr,
2691 struct state_list **true_stack,
2692 struct state_list **false_stack)
2693 {
2694 struct sm_state *sm;
2695 char *left, *right;
2696 int op;
2697 static char buf[256];
2698
2699 if (expr->type != EXPR_COMPARE)
2700 return NULL;
2701
2702 op = expr->op;
2703
2704 left = expr_to_var(expr->left);
2705 right = expr_to_var(expr->right);
2706 if (!left || !right) {
2707 free_string(left);
2708 free_string(right);
2709 return NULL;
2710 }
2711
2712 if (strcmp(left, right) > 0) {
2713 char *tmp = left;
2714
2715 left = right;
2716 right = tmp;
2717 op = flip_comparison(op);
2718 }
2719
2720 snprintf(buf, sizeof(buf), "%s vs %s", left, right);
2721 sm = get_sm_state(compare_id, buf, NULL);
2722 if (!sm)
2723 return NULL;
2724 if (!sm->merged)
2725 return NULL;
2726
2727 filter_by_sm(sm, op, true_stack, false_stack);
2728 if (!*true_stack && !*false_stack)
2729 return NULL;
2730
2731 if (debug_implied())
2732 sm_msg("implications from comparison: (%s)", show_sm(sm));
2733
2734 return sm;
2735 }
|
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 */
17
18 /*
19 * The point here is to store the relationships between two variables.
20 * Ie: y > x.
21 * To do that we create a state with the two variables in alphabetical order:
22 * ->name = "x vs y" and the state would be "<". On the false path the state
23 * would be ">=".
24 *
25 * Part of the trick of it is that if x or y is modified then we need to reset
26 * the state. We need to keep a list of all the states which depend on x and
27 * all the states which depend on y. The link_id code handles this.
28 *
29 */
30
31 #include "smatch.h"
32 #include "smatch_extra.h"
33 #include "smatch_slist.h"
34
35 int comparison_id;
36 static int link_id;
37 static int inc_dec_id;
38 static int inc_dec_link_id;
39
40 static void add_comparison(struct expression *left, int comparison, struct expression *right);
41
42 /* for handling for loops */
43 STATE(start);
44 STATE(incremented);
45
46 ALLOCATOR(compare_data, "compare data");
47
48 static struct symbol *vsl_to_sym(struct var_sym_list *vsl)
49 {
50 struct var_sym *vs;
51
52 if (!vsl)
53 return NULL;
54 if (ptr_list_size((struct ptr_list *)vsl) != 1)
55 return NULL;
525 if (GT && LT)
526 return IMPOSSIBLE_COMPARISON;
527 if (GT && NE)
528 return '>';
529 if (LT && NE)
530 return '<';
531 if (NE == 2)
532 return SPECIAL_NOTEQUAL;
533 if (total == 2 && (LT || GT) && EQ)
534 return IMPOSSIBLE_COMPARISON;
535
536 return UNKNOWN_COMPARISON;
537 }
538
539 static void pre_merge_hook(struct sm_state *cur, struct sm_state *other)
540 {
541 struct compare_data *data = cur->state->data;
542 int extra, new;
543 static bool in_recurse;
544
545 // FIXME. No data is useless
546 if (!data)
547 return;
548
549 if (in_recurse)
550 return;
551 in_recurse = true;
552 extra = comparison_from_extra(data->left, data->right);
553 in_recurse = false;
554 if (!extra)
555 return;
556 new = comparison_intersection(extra, data->comparison);
557 if (new == data->comparison)
558 return;
559
560 // FIXME: we should always preserve implications
561 set_state(comparison_id, cur->name, NULL,
562 alloc_compare_state(data->left, data->left_var, data->left_vsl,
563 new,
564 data->right, data->right_var, data->right_vsl));
565 }
566
567 struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
568 {
569 struct compare_data *data = s1->data;
570 int op;
571
572 if (!data)
573 return &undefined;
574
575 op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
576 return alloc_compare_state(
577 data->left, data->left_var, data->left_vsl,
578 op,
579 data->right, data->right_var, data->right_vsl);
580 }
581
609 char orig[64];
610 char state_name[128];
611 struct smatch_state *state;
612 struct string_list *links;
613 char *link;
614
615 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
616 struct var_sym_list *left_vsl = NULL;
617 struct var_sym_list *right_vsl = NULL;
618
619 if (!param->ident)
620 continue;
621 snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
622 snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
623 add_var_sym(&left_vsl, param->ident->name, param);
624 add_var_sym(&right_vsl, orig, param);
625 state = alloc_compare_state(
626 NULL, param->ident->name, left_vsl,
627 SPECIAL_EQUAL,
628 NULL, alloc_sname(orig), right_vsl);
629 set_state(comparison_id, state_name, NULL, state);
630
631 link = alloc_sname(state_name);
632 links = NULL;
633 insert_string(&links, link);
634 state = alloc_link_state(links);
635 set_state(link_id, param->ident->name, param, state);
636 } END_FOR_EACH_PTR(param);
637 }
638
639 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
640 {
641 struct smatch_state *ret;
642 struct string_list *links;
643
644 links = combine_string_lists(s1->data, s2->data);
645 ret = alloc_link_state(links);
646 return ret;
647 }
648
649 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
660
661 new = alloc_sname(link);
662 insert_string(&links, new);
663
664 new_state = alloc_link_state(links);
665 set_state(link_id, var, sym, new_state);
666 }
667
668 static void match_inc(struct sm_state *sm, bool preserve)
669 {
670 struct string_list *links;
671 struct smatch_state *state, *new;
672 struct compare_data *data;
673 char *tmp;
674 int flip;
675 int op;
676
677 links = sm->state->data;
678
679 FOR_EACH_PTR(links, tmp) {
680 state = get_state(comparison_id, tmp, NULL);
681 if (!state)
682 continue;
683 data = state->data;
684 if (!data)
685 continue;
686
687 flip = 0;
688 if (strncmp(sm->name, tmp, strlen(sm->name)) != 0 ||
689 tmp[strlen(sm->name)] != ' ')
690 flip = 1;
691
692 op = state_to_comparison(state);
693
694 switch (flip ? flip_comparison(op) : op) {
695 case SPECIAL_EQUAL:
696 case SPECIAL_GTE:
697 case SPECIAL_UNSIGNED_GTE:
698 case '>':
699 case SPECIAL_UNSIGNED_GT:
700 if (preserve)
701 break;
702 new = alloc_compare_state(
703 data->left, data->left_var, data->left_vsl,
704 flip ? '<' : '>',
705 data->right, data->right_var, data->right_vsl);
706 set_state(comparison_id, tmp, NULL, new);
707 break;
708 case '<':
709 case SPECIAL_UNSIGNED_LT:
710 new = alloc_compare_state(
711 data->left, data->left_var, data->left_vsl,
712 flip ? SPECIAL_GTE : SPECIAL_LTE,
713 data->right, data->right_var, data->right_vsl);
714 set_state(comparison_id, tmp, NULL, new);
715 break;
716 default:
717 new = alloc_compare_state(
718 data->left, data->left_var, data->left_vsl,
719 UNKNOWN_COMPARISON,
720 data->right, data->right_var, data->right_vsl);
721 set_state(comparison_id, tmp, NULL, new);
722 }
723 } END_FOR_EACH_PTR(tmp);
724 }
725
726 static void match_dec(struct sm_state *sm, bool preserve)
727 {
728 struct string_list *links;
729 struct smatch_state *state;
730 char *tmp;
731
732 links = sm->state->data;
733
734 FOR_EACH_PTR(links, tmp) {
735 struct compare_data *data;
736 struct smatch_state *new;
737
738 state = get_state(comparison_id, tmp, NULL);
739 if (!state || !state->data)
740 continue;
741
742 data = state->data;
743
744 switch (state_to_comparison(state)) {
745 case SPECIAL_EQUAL:
746 case SPECIAL_LTE:
747 case SPECIAL_UNSIGNED_LTE:
748 case '<':
749 case SPECIAL_UNSIGNED_LT: {
750 if (preserve)
751 break;
752
753 new = alloc_compare_state(
754 data->left, data->left_var, data->left_vsl,
755 '<',
756 data->right, data->right_var, data->right_vsl);
757 set_state(comparison_id, tmp, NULL, new);
758 break;
759 }
760 default:
761 new = alloc_compare_state(
762 data->left, data->left_var, data->left_vsl,
763 UNKNOWN_COMPARISON,
764 data->right, data->right_var, data->right_vsl);
765 set_state(comparison_id, tmp, NULL, new);
766 }
767 } END_FOR_EACH_PTR(tmp);
768 }
769
770 static void reset_sm(struct sm_state *sm)
771 {
772 struct string_list *links;
773 char *tmp;
774
775 links = sm->state->data;
776
777 FOR_EACH_PTR(links, tmp) {
778 struct smatch_state *old, *new;
779
780 old = get_state(comparison_id, tmp, NULL);
781 if (!old || !old->data) {
782 new = &undefined;
783 } else {
784 struct compare_data *data = old->data;
785
786 new = alloc_compare_state(
787 data->left, data->left_var, data->left_vsl,
788 UNKNOWN_COMPARISON,
789 data->right, data->right_var, data->right_vsl);
790 }
791 set_state(comparison_id, tmp, NULL, new);
792 } END_FOR_EACH_PTR(tmp);
793 set_state(link_id, sm->name, sm->sym, &undefined);
794 }
795
796 static bool match_add_sub_assign(struct sm_state *sm, struct expression *expr)
797 {
798 struct range_list *rl;
799 sval_t zero = { .type = &int_ctype };
800
801 if (!expr || expr->type != EXPR_ASSIGNMENT)
802 return false;
803 if (expr->op != SPECIAL_ADD_ASSIGN && expr->op != SPECIAL_SUB_ASSIGN)
804 return false;
805
806 get_absolute_rl(expr->right, &rl);
807 if (sval_is_negative(rl_min(rl))) {
808 reset_sm(sm);
809 return false;
810 }
811
973 save_link_var_sym(var, sym, link);
974 free_string(var);
975 }
976
977 static int get_orig_comparison(struct stree *pre_stree, const char *left, const char *right)
978 {
979 struct smatch_state *state;
980 struct compare_data *data;
981 int flip = 0;
982 char state_name[256];
983
984 if (strcmp(left, right) > 0) {
985 const char *tmp = right;
986
987 flip = 1;
988 right = left;
989 left = tmp;
990 }
991
992 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
993 state = get_state_stree(pre_stree, comparison_id, state_name, NULL);
994 if (!state || !state->data)
995 return 0;
996 data = state->data;
997 if (flip)
998 return flip_comparison(data->comparison);
999 return data->comparison;
1000
1001 }
1002
1003 static int have_common_var_sym(struct var_sym_list *left_vsl, struct var_sym_list *right_vsl)
1004 {
1005 struct var_sym *tmp;
1006
1007 FOR_EACH_PTR(left_vsl, tmp) {
1008 if (in_var_sym_list(right_vsl, tmp->var, tmp->sym))
1009 return 1;
1010 } END_FOR_EACH_PTR(tmp);
1011
1012 return 0;
1013 }
1026 const char *left_var, struct var_sym_list *left_vsl,
1027 int left_comparison, int left_false_comparison,
1028 const char *mid_var, struct var_sym_list *mid_vsl,
1029 struct string_list *links)
1030 {
1031 struct smatch_state *state;
1032 struct smatch_state *true_state, *false_state;
1033 struct compare_data *data;
1034 struct expression *right_expr;
1035 const char *right_var;
1036 struct var_sym_list *right_vsl;
1037 int orig_comparison;
1038 int right_comparison;
1039 int true_comparison;
1040 int false_comparison;
1041 char *tmp;
1042 char state_name[256];
1043 struct var_sym *vs;
1044
1045 FOR_EACH_PTR(links, tmp) {
1046 state = get_state_stree(pre_stree, comparison_id, tmp, NULL);
1047 if (!state || !state->data)
1048 continue;
1049 data = state->data;
1050 right_comparison = data->comparison;
1051 right_expr = data->right;
1052 right_var = data->right_var;
1053 right_vsl = data->right_vsl;
1054 if (strcmp(mid_var, right_var) == 0) {
1055 right_expr = data->left;
1056 right_var = data->left_var;
1057 right_vsl = data->left_vsl;
1058 right_comparison = flip_comparison(right_comparison);
1059 }
1060 if (have_common_var_sym(left_vsl, right_vsl))
1061 continue;
1062
1063 orig_comparison = get_orig_comparison(pre_stree, left_var, right_var);
1064
1065 true_comparison = combine_comparisons(left_comparison, right_comparison);
1066 false_comparison = combine_comparisons(left_false_comparison, right_comparison);
1085
1086 if (!true_comparison && !false_comparison)
1087 continue;
1088
1089 if (true_comparison)
1090 true_state = alloc_compare_state(
1091 left_expr, left_var, left_vsl,
1092 true_comparison,
1093 right_expr, right_var, right_vsl);
1094 else
1095 true_state = NULL;
1096 if (false_comparison)
1097 false_state = alloc_compare_state(
1098 left_expr, left_var, left_vsl,
1099 false_comparison,
1100 right_expr, right_var, right_vsl);
1101 else
1102 false_state = NULL;
1103
1104 snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var);
1105 set_true_false_states(comparison_id, state_name, NULL, true_state, false_state);
1106 FOR_EACH_PTR(left_vsl, vs) {
1107 save_link_var_sym(vs->var, vs->sym, state_name);
1108 } END_FOR_EACH_PTR(vs);
1109 FOR_EACH_PTR(right_vsl, vs) {
1110 save_link_var_sym(vs->var, vs->sym, state_name);
1111 } END_FOR_EACH_PTR(vs);
1112 if (!vsl_to_sym(left_vsl))
1113 save_link_var_sym(left_var, NULL, state_name);
1114 if (!vsl_to_sym(right_vsl))
1115 save_link_var_sym(right_var, NULL, state_name);
1116 } END_FOR_EACH_PTR(tmp);
1117 }
1118
1119 static void update_tf_data(struct stree *pre_stree,
1120 struct expression *left_expr,
1121 const char *left_name, struct var_sym_list *left_vsl,
1122 struct expression *right_expr,
1123 const char *right_name, struct var_sym_list *right_vsl,
1124 int true_comparison, int false_comparison)
1125 {
1184 store_link(inc_dec_link_id, cap_name, cap_sym, iter_name, iter_sym);
1185
1186 free_string(iter_name);
1187 free_string(cap_name);
1188 return;
1189 }
1190
1191 /* Second time checking the condtion */
1192 if (__prev_stmt != __cur_stmt->iterator_post_statement)
1193 return;
1194
1195 if (get_state_chunk(inc_dec_id, expr->left) != &incremented)
1196 return;
1197
1198 data = false_state->data;
1199 false_state = alloc_compare_state(
1200 data->left, data->left_var, data->left_vsl,
1201 SPECIAL_EQUAL,
1202 data->right, data->right_var, data->right_vsl);
1203
1204 // FIXME: This doesn't handle links correct so it doesn't set "param orig"
1205 set_true_false_states(comparison_id, state_name, NULL, NULL, false_state);
1206 }
1207
1208 static int is_plus_one(struct expression *expr)
1209 {
1210 sval_t sval;
1211
1212 if (expr->type != EXPR_BINOP || expr->op != '+')
1213 return 0;
1214 if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1215 return 0;
1216 return 1;
1217 }
1218
1219 static int is_minus_one(struct expression *expr)
1220 {
1221 sval_t sval;
1222
1223 if (expr->type != EXPR_BINOP || expr->op != '-')
1224 return 0;
1225 if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1326 }
1327
1328 orig_comparison = get_comparison(left_expr, right_expr);
1329 op = comparison_intersection(orig_comparison, op);
1330 false_op = comparison_intersection(orig_comparison, false_op);
1331
1332 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
1333 true_state = alloc_compare_state(
1334 left_expr, left, left_vsl,
1335 op,
1336 right_expr, right, right_vsl);
1337 false_state = alloc_compare_state(
1338 left_expr, left, left_vsl,
1339 false_op,
1340 right_expr, right, right_vsl);
1341
1342 pre_stree = clone_stree(__get_cur_stree());
1343 update_tf_data(pre_stree, left_expr, left, left_vsl, right_expr, right, right_vsl, op, false_op);
1344 free_stree(&pre_stree);
1345
1346 set_true_false_states(comparison_id, state_name, NULL, true_state, false_state);
1347 __compare_param_limit_hook(left_expr, right_expr, state_name, true_state, false_state);
1348 save_link(left_expr, state_name);
1349 save_link(right_expr, state_name);
1350
1351 if (_false_state)
1352 *_false_state = false_state;
1353 if (_state_name)
1354 *_state_name = state_name;
1355 free:
1356 free_string(left);
1357 free_string(right);
1358 }
1359
1360 void __comparison_match_condition(struct expression *expr)
1361 {
1362 struct expression *left, *right, *new_left, *new_right, *tmp;
1363 struct smatch_state *false_state = NULL;
1364 char *state_name = NULL;
1365 int redo, count;
1366
1428
1429 if (strcmp(left_name, right_name) > 0) {
1430 struct expression *tmp_expr = left_expr;
1431 const char *tmp_name = left_name;
1432 struct var_sym_list *tmp_vsl = left_vsl;
1433
1434 left_expr = right_expr;
1435 left_name = right_name;
1436 left_vsl = right_vsl;
1437 right_expr = tmp_expr;
1438 right_name = tmp_name;
1439 right_vsl = tmp_vsl;
1440 comparison = flip_comparison(comparison);
1441 }
1442 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1443 state = alloc_compare_state(
1444 left_expr, left_name, left_vsl,
1445 comparison,
1446 right_expr, right_name, right_vsl);
1447
1448 set_state(comparison_id, state_name, NULL, state);
1449
1450 FOR_EACH_PTR(left_vsl, vs) {
1451 save_link_var_sym(vs->var, vs->sym, state_name);
1452 } END_FOR_EACH_PTR(vs);
1453 FOR_EACH_PTR(right_vsl, vs) {
1454 save_link_var_sym(vs->var, vs->sym, state_name);
1455 } END_FOR_EACH_PTR(vs);
1456 }
1457
1458 static void add_comparison(struct expression *left, int comparison, struct expression *right)
1459 {
1460 char *left_name = NULL;
1461 char *right_name = NULL;
1462 struct symbol *left_sym, *right_sym;
1463 struct var_sym_list *left_vsl, *right_vsl;
1464 struct smatch_state *state;
1465 char state_name[256];
1466
1467 left_name = chunk_to_var_sym(left, &left_sym);
1468 if (!left_name)
1478 struct symbol *tmp_sym = left_sym;
1479 char *tmp_name = left_name;
1480 struct var_sym_list *tmp_vsl = left_vsl;
1481
1482 left = right;
1483 left_name = right_name;
1484 left_sym = right_sym;
1485 left_vsl = right_vsl;
1486 right = tmp_expr;
1487 right_name = tmp_name;
1488 right_sym = tmp_sym;
1489 right_vsl = tmp_vsl;
1490 comparison = flip_comparison(comparison);
1491 }
1492 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1493 state = alloc_compare_state(
1494 left, left_name, left_vsl,
1495 comparison,
1496 right, right_name, right_vsl);
1497
1498 set_state(comparison_id, state_name, NULL, state);
1499 save_link(left, state_name);
1500 save_link(right, state_name);
1501
1502 free:
1503 free_string(left_name);
1504 free_string(right_name);
1505 }
1506
1507 static void match_assign_add(struct expression *expr)
1508 {
1509 struct expression *right;
1510 struct expression *r_left, *r_right;
1511 sval_t left_tmp, right_tmp;
1512
1513 right = strip_expr(expr->right);
1514 r_left = strip_expr(right->left);
1515 r_right = strip_expr(right->right);
1516
1517 get_absolute_min(r_left, &left_tmp);
1518 get_absolute_min(r_right, &right_tmp);
1595 struct expression *expr;
1596 const char *var;
1597 struct var_sym_list *vsl;
1598 int comparison;
1599 char *tmp;
1600
1601 left_var = chunk_to_var_sym(left, &left_sym);
1602 if (!left_var)
1603 goto done;
1604 left_vsl = expr_to_vsl(left);
1605 right_var = chunk_to_var_sym(right, &right_sym);
1606 if (!right_var)
1607 goto done;
1608
1609 state = get_state(link_id, right_var, right_sym);
1610 if (!state)
1611 return;
1612 links = state->data;
1613
1614 FOR_EACH_PTR(links, tmp) {
1615 state = get_state(comparison_id, tmp, NULL);
1616 if (!state || !state->data)
1617 continue;
1618 data = state->data;
1619 comparison = data->comparison;
1620 expr = data->right;
1621 var = data->right_var;
1622 vsl = data->right_vsl;
1623 if (strcmp(var, right_var) == 0) {
1624 expr = data->left;
1625 var = data->left_var;
1626 vsl = data->left_vsl;
1627 comparison = flip_comparison(comparison);
1628 }
1629 /* n = copy_from_user(dest, src, n); leads to n <= n which is nonsense */
1630 if (strcmp(left_var, var) == 0)
1631 continue;
1632 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1633 } END_FOR_EACH_PTR(tmp);
1634
1635 done:
1664 char buf[256];
1665 struct smatch_state *state;
1666 int invert = 0;
1667 int ret = 0;
1668
1669 if (!one || !two)
1670 return UNKNOWN_COMPARISON;
1671
1672 if (strcmp(one, two) == 0)
1673 return SPECIAL_EQUAL;
1674
1675 if (strcmp(one, two) > 0) {
1676 const char *tmp = one;
1677
1678 one = two;
1679 two = tmp;
1680 invert = 1;
1681 }
1682
1683 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1684 state = get_state(comparison_id, buf, NULL);
1685 if (state)
1686 ret = state_to_comparison(state);
1687
1688 if (invert)
1689 ret = flip_comparison(ret);
1690
1691 return ret;
1692 }
1693
1694 static int get_comparison_helper(struct expression *a, struct expression *b, bool use_extra)
1695 {
1696 char *one = NULL;
1697 char *two = NULL;
1698 int ret = UNKNOWN_COMPARISON;
1699 int extra = UNKNOWN_COMPARISON;
1700
1701 if (a == UNKNOWN_COMPARISON ||
1702 b == UNKNOWN_COMPARISON)
1703 return UNKNOWN_COMPARISON;
1704
1770 goto free;
1771 two = chunk_to_var(b);
1772 if (!two)
1773 goto free;
1774
1775
1776 if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
1777 ret = 1;
1778 goto free;
1779 }
1780
1781 if (strcmp(one, two) > 0) {
1782 char *tmp = one;
1783
1784 one = two;
1785 two = tmp;
1786 comparison = flip_comparison(comparison);
1787 }
1788
1789 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1790 sm = get_sm_state(comparison_id, buf, NULL);
1791 if (!sm)
1792 goto free;
1793
1794 FOR_EACH_PTR(sm->possible, sm) {
1795 if (!sm->state->data)
1796 continue;
1797 saved = ((struct compare_data *)sm->state->data)->comparison;
1798 if (saved == comparison)
1799 ret = 1;
1800 if (comparison == SPECIAL_EQUAL &&
1801 (saved == SPECIAL_LTE ||
1802 saved == SPECIAL_GTE ||
1803 saved == SPECIAL_UNSIGNED_LTE ||
1804 saved == SPECIAL_UNSIGNED_GTE))
1805 ret = 1;
1806 if (ret == 1)
1807 goto free;
1808 } END_FOR_EACH_PTR(sm);
1809
1810 return ret;
1811 free:
1812 free_string(one);
1813 free_string(two);
1814 return ret;
1815 }
1816
1817 struct state_list *get_all_comparisons(struct expression *expr)
1818 {
1819 struct smatch_state *state;
1820 struct string_list *links;
1821 struct state_list *ret = NULL;
1822 struct sm_state *sm;
1823 char *tmp;
1824
1825 state = get_state_chunk(link_id, expr);
1826 if (!state)
1827 return NULL;
1828 links = state->data;
1829
1830 FOR_EACH_PTR(links, tmp) {
1831 sm = get_sm_state(comparison_id, tmp, NULL);
1832 if (!sm)
1833 continue;
1834 // FIXME have to compare name with vsl
1835 add_ptr_list(&ret, sm);
1836 } END_FOR_EACH_PTR(tmp);
1837
1838 return ret;
1839 }
1840
1841 struct state_list *get_all_possible_equal_comparisons(struct expression *expr)
1842 {
1843 struct smatch_state *state;
1844 struct string_list *links;
1845 struct state_list *ret = NULL;
1846 struct sm_state *sm;
1847 char *tmp;
1848
1849 state = get_state_chunk(link_id, expr);
1850 if (!state)
1851 return NULL;
1852 links = state->data;
1853
1854 FOR_EACH_PTR(links, tmp) {
1855 sm = get_sm_state(comparison_id, tmp, NULL);
1856 if (!sm)
1857 continue;
1858 if (!strchr(sm->state->name, '='))
1859 continue;
1860 if (strcmp(sm->state->name, "!=") == 0)
1861 continue;
1862 add_ptr_list(&ret, sm);
1863 } END_FOR_EACH_PTR(tmp);
1864
1865 return ret;
1866 }
1867
1868 struct state_list *get_all_possible_not_equal_comparisons(struct expression *expr)
1869 {
1870 struct smatch_state *state;
1871 struct string_list *links;
1872 struct state_list *ret = NULL;
1873 struct sm_state *sm;
1874 struct sm_state *possible;
1875 char *link;
1876
1877 return NULL;
1878
1879 state = get_state_chunk(link_id, expr);
1880 if (!state)
1881 return NULL;
1882 links = state->data;
1883
1884 FOR_EACH_PTR(links, link) {
1885 sm = get_sm_state(comparison_id, link, NULL);
1886 if (!sm)
1887 continue;
1888 FOR_EACH_PTR(sm->possible, possible) {
1889 if (strcmp(possible->state->name, "!=") != 0)
1890 continue;
1891 add_ptr_list(&ret, sm);
1892 break;
1893 } END_FOR_EACH_PTR(link);
1894 } END_FOR_EACH_PTR(link);
1895
1896 return ret;
1897 }
1898
1899 static void update_links_from_call(struct expression *left,
1900 int left_compare,
1901 struct expression *right)
1902 {
1903 struct string_list *links;
1904 struct smatch_state *state;
1905 struct compare_data *data;
1910 struct expression *expr;
1911 const char *var;
1912 struct var_sym_list *vsl;
1913 int comparison;
1914 char *tmp;
1915
1916 left_var = chunk_to_var_sym(left, &left_sym);
1917 if (!left_var)
1918 goto done;
1919 left_vsl = expr_to_vsl(left);
1920 right_var = chunk_to_var_sym(right, &right_sym);
1921 if (!right_var)
1922 goto done;
1923
1924 state = get_state(link_id, right_var, right_sym);
1925 if (!state)
1926 return;
1927 links = state->data;
1928
1929 FOR_EACH_PTR(links, tmp) {
1930 state = get_state(comparison_id, tmp, NULL);
1931 if (!state || !state->data)
1932 continue;
1933 data = state->data;
1934 comparison = data->comparison;
1935 expr = data->right;
1936 var = data->right_var;
1937 vsl = data->right_vsl;
1938 if (strcmp(var, right_var) == 0) {
1939 expr = data->left;
1940 var = data->left_var;
1941 vsl = data->left_vsl;
1942 comparison = flip_comparison(comparison);
1943 }
1944 comparison = combine_comparisons(left_compare, comparison);
1945 if (!comparison)
1946 continue;
1947 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1948 } END_FOR_EACH_PTR(tmp);
1949
1950 done:
2159 char *link;
2160 char info_buf[256];
2161 int i;
2162
2163 i = -1;
2164 FOR_EACH_PTR(expr->args, arg) {
2165 i++;
2166
2167 state = get_state_chunk(link_id, arg);
2168 if (!state)
2169 continue;
2170
2171 links = state->data;
2172 FOR_EACH_PTR(links, link) {
2173 struct var_sym_list *right_vsl;
2174 struct var_sym *right_vs;
2175
2176
2177 if (strstr(link, " orig"))
2178 continue;
2179 sm = get_sm_state(comparison_id, link, NULL);
2180 if (!sm)
2181 continue;
2182 data = sm->state->data;
2183 if (!data ||
2184 data->comparison == UNKNOWN_COMPARISON ||
2185 data->comparison == IMPOSSIBLE_COMPARISON)
2186 continue;
2187 arg_name = expr_to_var(arg);
2188 if (!arg_name)
2189 continue;
2190
2191 right_vsl = NULL;
2192 if (strcmp(data->left_var, arg_name) == 0) {
2193 comparison = data->comparison;
2194 right_name = data->right_var;
2195 right_vsl = data->right_vsl;
2196 } else if (strcmp(data->right_var, arg_name) == 0) {
2197 comparison = flip_comparison(data->comparison);
2198 right_name = data->left_var;
2199 right_vsl = data->left_vsl;
2214 free_string(arg_name);
2215 } END_FOR_EACH_PTR(link);
2216 } END_FOR_EACH_PTR(arg);
2217 }
2218
2219 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *link_sm)
2220 {
2221 struct sm_state *compare_sm;
2222 struct string_list *links;
2223 char *link;
2224 struct compare_data *data;
2225 struct var_sym *left, *right;
2226 static char info_buf[256];
2227 const char *right_name;
2228
2229 if (strstr(printed_name, " orig"))
2230 return;
2231
2232 links = link_sm->state->data;
2233 FOR_EACH_PTR(links, link) {
2234 compare_sm = get_sm_state(comparison_id, link, NULL);
2235 if (!compare_sm)
2236 continue;
2237 data = compare_sm->state->data;
2238 if (!data || !data->comparison)
2239 continue;
2240
2241 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2242 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2243 continue;
2244 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2245 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2246 if (left->sym == right->sym &&
2247 strcmp(left->var, right->var) == 0)
2248 continue;
2249 /*
2250 * Both parameters link to this comparison so only
2251 * record the first one.
2252 */
2253 if (left->sym != link_sm->sym ||
2254 strcmp(left->var, link_sm->name) != 0)
2307 {
2308 struct sm_state *tmp;
2309 struct string_list *links;
2310 char *link;
2311 struct sm_state *sm;
2312 struct compare_data *data;
2313 struct var_sym *left, *right;
2314 int left_param, right_param;
2315 char left_buf[256];
2316 char right_buf[256];
2317 char info_buf[258];
2318 const char *tmp_name;
2319
2320 print_return_value_comparison(return_id, return_ranges, expr);
2321
2322 FOR_EACH_MY_SM(link_id, __get_cur_stree(), tmp) {
2323 if (get_param_num_from_sym(tmp->sym) < 0)
2324 continue;
2325 links = tmp->state->data;
2326 FOR_EACH_PTR(links, link) {
2327 sm = get_sm_state(comparison_id, link, NULL);
2328 if (!sm)
2329 continue;
2330 data = sm->state->data;
2331 if (!data ||
2332 data->comparison == UNKNOWN_COMPARISON ||
2333 data->comparison == IMPOSSIBLE_COMPARISON)
2334 continue;
2335 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2336 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2337 continue;
2338 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2339 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2340 if (left->sym == right->sym &&
2341 strcmp(left->var, right->var) == 0)
2342 continue;
2343 /*
2344 * Both parameters link to this comparison so only
2345 * record the first one.
2346 */
2347 if (left->sym != tmp->sym ||
2525 if (expr->type != EXPR_CALL)
2526 return 0;
2527
2528 if (!split_op_param_key(value, &op, &right_param, &right_key))
2529 return 0;
2530
2531 left_arg = get_argument_from_call_expr(expr->args, left_param);
2532 if (!left_arg)
2533 return 0;
2534
2535 right_arg = get_argument_from_call_expr(expr->args, right_param);
2536 if (!right_arg)
2537 return 0;
2538
2539 left_name = get_variable_from_key(left_arg, left_key, &left_sym);
2540 right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2541 if (!left_name || !right_name)
2542 goto free;
2543
2544 snprintf(buf, sizeof(buf), "%s vs %s", left_name, right_name);
2545 state = get_state(comparison_id, buf, NULL);
2546 if (!state)
2547 goto free;
2548 state_op = state_to_comparison(state);
2549 if (!state_op)
2550 goto free;
2551
2552 if (!comparison_intersection(remove_unsigned_from_comparison(state_op), op))
2553 ret = 1;
2554 free:
2555 free_string(left_name);
2556 free_string(right_name);
2557 return ret;
2558 }
2559
2560 int impossibly_high_comparison(struct expression *expr)
2561 {
2562 struct smatch_state *link_state;
2563 struct sm_state *sm;
2564 struct string_list *links;
2565 char *link;
2566 struct compare_data *data;
2567
2568 link_state = get_state_expr(link_id, expr);
2569 if (!link_state) {
2570 if (expr->type == EXPR_BINOP &&
2571 (impossibly_high_comparison(expr->left) ||
2572 impossibly_high_comparison(expr->right)))
2573 return 1;
2574 return 0;
2575 }
2576
2577 links = link_state->data;
2578 FOR_EACH_PTR(links, link) {
2579 sm = get_sm_state(comparison_id, link, NULL);
2580 if (!sm)
2581 continue;
2582 data = sm->state->data;
2583 if (!data)
2584 continue;
2585 if (!possibly_true(data->left, data->comparison, data->right))
2586 return 1;
2587 } END_FOR_EACH_PTR(link);
2588
2589 return 0;
2590 }
2591
2592 static void free_data(struct symbol *sym)
2593 {
2594 if (__inline_fn)
2595 return;
2596 clear_compare_data_alloc();
2597 }
2598
2599 void register_comparison(int id)
2600 {
2601 comparison_id = id;
2602 set_dynamic_states(comparison_id);
2603 add_hook(&save_start_states, AFTER_DEF_HOOK);
2604 add_unmatched_state_hook(comparison_id, unmatched_comparison);
2605 add_pre_merge_hook(comparison_id, &pre_merge_hook);
2606 add_merge_hook(comparison_id, &merge_compare_states);
2607 add_hook(&free_data, AFTER_FUNC_HOOK);
2608 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2609 add_split_return_callback(&print_return_comparison);
2610
2611 select_return_states_hook(PARAM_COMPARE, &db_return_comparison);
2612 add_hook(&match_preop, OP_HOOK);
2613 }
2614
2615 void register_comparison_late(int id)
2616 {
2617 add_hook(&match_assign, ASSIGNMENT_HOOK);
2618 }
2619
2620 void register_comparison_links(int id)
2621 {
2622 link_id = id;
2623 db_ignore_states(link_id);
2624 set_dynamic_states(link_id);
2625 add_merge_hook(link_id, &merge_links);
2626 add_modification_hook(link_id, &match_modify);
2627 add_modification_hook_late(link_id, match_inc_dec);
2628
2629 add_member_info_callback(link_id, struct_member_callback);
2630 }
2631
2632 void register_comparison_inc_dec(int id)
2633 {
2634 inc_dec_id = id;
2635 add_modification_hook_late(inc_dec_id, &iter_modify);
2636 }
2637
2638 void register_comparison_inc_dec_links(int id)
2639 {
2640 inc_dec_link_id = id;
2641 set_dynamic_states(inc_dec_link_id);
2642 set_up_link_functions(inc_dec_id, inc_dec_link_id);
2643 }
2644
2645 static struct sm_state *clone_partial_sm(struct sm_state *sm, int comparison)
2646 {
2647 struct compare_data *data;
2648 struct sm_state *clone;
2649 struct stree *stree;
2650
2651 data = sm->state->data;
2652
2653 clone = clone_sm(sm);
2654 clone->state = alloc_compare_state(data->left, data->left_var, data->left_vsl,
2655 comparison,
2656 data->right, data->right_var, data->right_vsl);
2657 free_slist(&clone->possible);
2658 add_possible_sm(clone, clone);
2659
2660 stree = clone_stree(sm->pool);
2661 overwrite_sm_state_stree(&stree, clone);
2662 clone->pool = stree;
2663
2664 return clone;
2665 }
2666
2667 static void create_fake_history(struct sm_state *sm, int op,
2668 struct state_list **true_stack,
2669 struct state_list **false_stack)
2670 {
2671 struct sm_state *true_sm, *false_sm;
2672 struct compare_data *data;
2673 int true_comparison;
2674 int false_comparison;
2675
2676 data = sm->state->data;
2677
2678 if (is_merged(sm) || sm->left || sm->right)
2679 return;
2680
2681 true_comparison = comparison_intersection(data->comparison, op);
2682 false_comparison = comparison_intersection(data->comparison, negate_comparison(op));
2683
2684 true_sm = clone_partial_sm(sm, true_comparison);
2685 false_sm = clone_partial_sm(sm, false_comparison);
2686
2687 sm->merged = 1;
2688 sm->left = true_sm;
2689 sm->right = false_sm;
2690
2691 add_ptr_list(true_stack, true_sm);
2692 add_ptr_list(false_stack, false_sm);
2693 }
2694
2695 static void filter_by_sm(struct sm_state *sm, int op,
2696 struct state_list **true_stack,
2697 struct state_list **false_stack,
2698 bool *useful)
2699 {
2700 struct compare_data *data;
2701 int is_true = 0;
2702 int is_false = 0;
2703
2704 if (!sm)
2705 return;
2706 data = sm->state->data;
2707 if (!data)
2708 goto split;
2709 if (data->comparison == IMPOSSIBLE_COMPARISON)
2710 return;
2711
2712 /*
2713 * We want to check that "data->comparison" is totally inside "op". So
2714 * if data->comparison is < and op is <= then that's true. Or if
2715 * data->comparison is == and op is <= then that's true. But if
2716 * data->comparison is <= and op is < than that's neither true nor
2717 * false.
2718 */
2719 if (data->comparison == comparison_intersection(data->comparison, op))
2720 is_true = 1;
2721 if (data->comparison == comparison_intersection(data->comparison, negate_comparison(op)))
2722 is_false = 1;
2723
2724 if (!is_true && !is_false && !is_merged(sm)) {
2725 create_fake_history(sm, op, true_stack, false_stack);
2726 return;
2727 }
2728
2729 if (debug_implied()) {
2730 sm_msg("%s: %s: op = '%s' negated '%s'. true_intersect = '%s' false_insersect = '%s' sm = '%s'",
2731 __func__,
2732 sm->state->name,
2733 alloc_sname(show_comparison(op)),
2734 alloc_sname(show_comparison(negate_comparison(op))),
2735 alloc_sname(show_comparison(comparison_intersection(data->comparison, op))),
2736 alloc_sname(show_comparison(comparison_intersection(data->comparison, negate_comparison(op)))),
2737 show_sm(sm));
2738 }
2739
2740 *useful = true;
2741 if (is_true)
2742 add_ptr_list(true_stack, sm);
2743 if (is_false)
2744 add_ptr_list(false_stack, sm);
2745 split:
2746 filter_by_sm(sm->left, op, true_stack, false_stack, useful);
2747 filter_by_sm(sm->right, op, true_stack, false_stack, useful);
2748 }
2749
2750 struct sm_state *comparison_implication_hook(struct expression *expr,
2751 struct state_list **true_stack,
2752 struct state_list **false_stack)
2753 {
2754 struct sm_state *sm;
2755 char *left, *right;
2756 int op;
2757 static char buf[256];
2758 bool useful = false;
2759
2760 if (expr->type != EXPR_COMPARE)
2761 return NULL;
2762
2763 op = expr->op;
2764
2765 left = expr_to_var(expr->left);
2766 right = expr_to_var(expr->right);
2767 if (!left || !right) {
2768 free_string(left);
2769 free_string(right);
2770 return NULL;
2771 }
2772
2773 if (strcmp(left, right) > 0) {
2774 char *tmp = left;
2775
2776 left = right;
2777 right = tmp;
2778 op = flip_comparison(op);
2779 }
2780
2781 snprintf(buf, sizeof(buf), "%s vs %s", left, right);
2782 sm = get_sm_state(comparison_id, buf, NULL);
2783 if (!sm)
2784 return NULL;
2785 if (!sm->merged)
2786 return NULL;
2787
2788 filter_by_sm(sm, op, true_stack, false_stack, &useful);
2789 if (!useful)
2790 return NULL;
2791
2792 if (debug_implied())
2793 sm_msg("implications from comparison: (%s)", show_sm(sm));
2794
2795 return sm;
2796 }
|