Print this page
new smatch
*** 55,64 ****
--- 55,73 ----
return NULL;
vs = first_ptr_list((struct ptr_list *)vsl);
return vs->sym;
}
+ static const char *show_comparison(int comparison)
+ {
+ if (comparison == IMPOSSIBLE_COMPARISON)
+ return "impossible";
+ if (comparison == UNKNOWN_COMPARISON)
+ return "unknown";
+ return show_special(comparison);
+ }
+
struct smatch_state *alloc_compare_state(
struct expression *left,
const char *left_var, struct var_sym_list *left_vsl,
int comparison,
struct expression *right,
*** 66,76 ****
{
struct smatch_state *state;
struct compare_data *data;
state = __alloc_smatch_state(0);
! state->name = alloc_sname(show_special(comparison));
data = __alloc_compare_data(0);
data->left = left;
data->left_var = alloc_sname(left_var);
data->left_vsl = clone_var_sym_list(left_vsl);
data->comparison = comparison;
--- 75,85 ----
{
struct smatch_state *state;
struct compare_data *data;
state = __alloc_smatch_state(0);
! state->name = alloc_sname(show_comparison(comparison));
data = __alloc_compare_data(0);
data->left = left;
data->left_var = alloc_sname(left_var);
data->left_vsl = clone_var_sym_list(left_vsl);
data->comparison = comparison;
*** 82,103 ****
}
int state_to_comparison(struct smatch_state *state)
{
if (!state || !state->data)
! return 0;
return ((struct compare_data *)state->data)->comparison;
}
/*
* flip_comparison() reverses the op left and right. So "x >= y" becomes "y <= x".
*/
int flip_comparison(int op)
{
switch (op) {
! case 0:
! return 0;
case '<':
return '>';
case SPECIAL_UNSIGNED_LT:
return SPECIAL_UNSIGNED_GT;
case SPECIAL_LTE:
--- 91,112 ----
}
int state_to_comparison(struct smatch_state *state)
{
if (!state || !state->data)
! return UNKNOWN_COMPARISON;
return ((struct compare_data *)state->data)->comparison;
}
/*
* flip_comparison() reverses the op left and right. So "x >= y" becomes "y <= x".
*/
int flip_comparison(int op)
{
switch (op) {
! case UNKNOWN_COMPARISON:
! return UNKNOWN_COMPARISON;
case '<':
return '>';
case SPECIAL_UNSIGNED_LT:
return SPECIAL_UNSIGNED_GT;
case SPECIAL_LTE:
*** 114,134 ****
return SPECIAL_UNSIGNED_LTE;
case '>':
return '<';
case SPECIAL_UNSIGNED_GT:
return SPECIAL_UNSIGNED_LT;
default:
sm_perror("unhandled comparison %d", op);
return op;
}
}
int negate_comparison(int op)
{
switch (op) {
! case 0:
! return 0;
case '<':
return SPECIAL_GTE;
case SPECIAL_UNSIGNED_LT:
return SPECIAL_UNSIGNED_GTE;
case SPECIAL_LTE:
--- 123,145 ----
return SPECIAL_UNSIGNED_LTE;
case '>':
return '<';
case SPECIAL_UNSIGNED_GT:
return SPECIAL_UNSIGNED_LT;
+ case IMPOSSIBLE_COMPARISON:
+ return UNKNOWN_COMPARISON;
default:
sm_perror("unhandled comparison %d", op);
return op;
}
}
int negate_comparison(int op)
{
switch (op) {
! case UNKNOWN_COMPARISON:
! return UNKNOWN_COMPARISON;
case '<':
return SPECIAL_GTE;
case SPECIAL_UNSIGNED_LT:
return SPECIAL_UNSIGNED_GTE;
case SPECIAL_LTE:
*** 145,154 ****
--- 156,167 ----
return SPECIAL_UNSIGNED_LT;
case '>':
return SPECIAL_LTE;
case SPECIAL_UNSIGNED_GT:
return SPECIAL_UNSIGNED_LTE;
+ case IMPOSSIBLE_COMPARISON:
+ return UNKNOWN_COMPARISON;
default:
sm_perror("unhandled comparison %d", op);
return op;
}
}
*** 157,167 ****
{
sval_t left_min, left_max, right_min, right_max;
struct symbol *type = &int_ctype;
if (!left_rl || !right_rl)
! return 0;
if (type_positive_bits(rl_type(left_rl)) > type_positive_bits(type))
type = rl_type(left_rl);
if (type_positive_bits(rl_type(right_rl)) > type_positive_bits(type))
type = rl_type(right_rl);
--- 170,180 ----
{
sval_t left_min, left_max, right_min, right_max;
struct symbol *type = &int_ctype;
if (!left_rl || !right_rl)
! return UNKNOWN_COMPARISON;
if (type_positive_bits(rl_type(left_rl)) > type_positive_bits(type))
type = rl_type(left_rl);
if (type_positive_bits(rl_type(right_rl)) > type_positive_bits(type))
type = rl_type(right_rl);
*** 186,206 ****
if (sval_cmp(left_min, right_max) > 0)
return '>';
if (sval_cmp(left_min, right_max) == 0)
return SPECIAL_GTE;
! return 0;
}
static int comparison_from_extra(struct expression *a, struct expression *b)
{
struct range_list *left, *right;
if (!get_implied_rl(a, &left))
! return 0;
if (!get_implied_rl(b, &right))
! return 0;
return rl_comparison(left, right);
}
static struct range_list *get_orig_rl(struct var_sym_list *vsl)
--- 199,219 ----
if (sval_cmp(left_min, right_max) > 0)
return '>';
if (sval_cmp(left_min, right_max) == 0)
return SPECIAL_GTE;
! return UNKNOWN_COMPARISON;
}
static int comparison_from_extra(struct expression *a, struct expression *b)
{
struct range_list *left, *right;
if (!get_implied_rl(a, &left))
! return UNKNOWN_COMPARISON;
if (!get_implied_rl(b, &right))
! return UNKNOWN_COMPARISON;
return rl_comparison(left, right);
}
static struct range_list *get_orig_rl(struct var_sym_list *vsl)
*** 219,251 ****
static struct smatch_state *unmatched_comparison(struct sm_state *sm)
{
struct compare_data *data = sm->state->data;
struct range_list *left_rl, *right_rl;
! int op;
if (!data)
return &undefined;
if (strstr(data->left_var, " orig"))
left_rl = get_orig_rl(data->left_vsl);
else if (!get_implied_rl_var_sym(data->left_var, vsl_to_sym(data->left_vsl), &left_rl))
! return &undefined;
if (strstr(data->right_var, " orig"))
right_rl = get_orig_rl(data->right_vsl);
else if (!get_implied_rl_var_sym(data->right_var, vsl_to_sym(data->right_vsl), &right_rl))
! return &undefined;
op = rl_comparison(left_rl, right_rl);
! if (op)
! return alloc_compare_state(
! data->left, data->left_var, data->left_vsl,
op,
data->right, data->right_var, data->right_vsl);
-
- return &undefined;
}
/* remove_unsigned_from_comparison() is obviously a hack. */
int remove_unsigned_from_comparison(int op)
{
--- 232,267 ----
static struct smatch_state *unmatched_comparison(struct sm_state *sm)
{
struct compare_data *data = sm->state->data;
struct range_list *left_rl, *right_rl;
! int op = UNKNOWN_COMPARISON;
if (!data)
return &undefined;
+ if (is_impossible_path()) {
+ op = IMPOSSIBLE_COMPARISON;
+ goto alloc;
+ }
+
if (strstr(data->left_var, " orig"))
left_rl = get_orig_rl(data->left_vsl);
else if (!get_implied_rl_var_sym(data->left_var, vsl_to_sym(data->left_vsl), &left_rl))
! goto alloc;
if (strstr(data->right_var, " orig"))
right_rl = get_orig_rl(data->right_vsl);
else if (!get_implied_rl_var_sym(data->right_var, vsl_to_sym(data->right_vsl), &right_rl))
! goto alloc;
op = rl_comparison(left_rl, right_rl);
!
! alloc:
! return alloc_compare_state(data->left, data->left_var, data->left_vsl,
op,
data->right, data->right_var, data->right_vsl);
}
/* remove_unsigned_from_comparison() is obviously a hack. */
int remove_unsigned_from_comparison(int op)
{
*** 269,281 ****
*/
int merge_comparisons(int one, int two)
{
int LT, EQ, GT;
! if (!one || !two)
! return 0;
one = remove_unsigned_from_comparison(one);
two = remove_unsigned_from_comparison(two);
if (one == two)
return one;
--- 285,302 ----
*/
int merge_comparisons(int one, int two)
{
int LT, EQ, GT;
! if (one == UNKNOWN_COMPARISON || two == UNKNOWN_COMPARISON)
! return UNKNOWN_COMPARISON;
+ if (one == IMPOSSIBLE_COMPARISON)
+ return two;
+ if (two == IMPOSSIBLE_COMPARISON)
+ return one;
+
one = remove_unsigned_from_comparison(one);
two = remove_unsigned_from_comparison(two);
if (one == two)
return one;
*** 319,329 ****
case '>':
GT = 1;
}
if (LT && EQ && GT)
! return 0;
if (LT && EQ)
return SPECIAL_LTE;
if (LT && GT)
return SPECIAL_NOTEQUAL;
if (LT)
--- 340,350 ----
case '>':
GT = 1;
}
if (LT && EQ && GT)
! return UNKNOWN_COMPARISON;
if (LT && EQ)
return SPECIAL_LTE;
if (LT && GT)
return SPECIAL_NOTEQUAL;
if (LT)
*** 330,350 ****
return '<';
if (EQ && GT)
return SPECIAL_GTE;
if (GT)
return '>';
! return 0;
}
/*
! * This is for if you have "a < b" and "b <= c". Or in other words,
! * "a < b <= c". You would call this like get_combined_comparison('<', '<=').
* The return comparison would be '<'.
- *
- * This function is different from merge_comparisons(), for example:
- * merge_comparison('<', '==') returns '<='
- * get_combined_comparison('<', '==') returns '<'
*/
int combine_comparisons(int left_compare, int right_compare)
{
int LT, EQ, GT;
--- 351,367 ----
return '<';
if (EQ && GT)
return SPECIAL_GTE;
if (GT)
return '>';
! return UNKNOWN_COMPARISON;
}
/*
! * This is for if you have "a < b" and "b <= c" and you want to see how "a
! * compares to c". You would call this like get_combined_comparison('<', '<=').
* The return comparison would be '<'.
*/
int combine_comparisons(int left_compare, int right_compare)
{
int LT, EQ, GT;
*** 398,560 ****
if (GT == 2) {
if (EQ == 2)
return SPECIAL_GTE;
return '>';
}
! return 0;
}
! int filter_comparison(int orig, int op)
{
! if (orig == op)
! return orig;
! orig = remove_unsigned_from_comparison(orig);
! op = remove_unsigned_from_comparison(op);
! switch (orig) {
! case 0:
! return op;
case '<':
! switch (op) {
! case '<':
case SPECIAL_LTE:
case SPECIAL_NOTEQUAL:
! return '<';
}
! return 0;
! case SPECIAL_LTE:
! switch (op) {
case '<':
case SPECIAL_LTE:
case SPECIAL_EQUAL:
! return op;
case SPECIAL_NOTEQUAL:
! return '<';
! }
! return 0;
! case SPECIAL_EQUAL:
! switch (op) {
! case SPECIAL_LTE:
! case SPECIAL_EQUAL:
case SPECIAL_GTE:
! case SPECIAL_UNSIGNED_LTE:
! case SPECIAL_UNSIGNED_GTE:
! return SPECIAL_EQUAL;
}
! return 0;
! case SPECIAL_NOTEQUAL:
! switch (op) {
! case '<':
! case SPECIAL_LTE:
return '<';
- case SPECIAL_UNSIGNED_LT:
- case SPECIAL_UNSIGNED_LTE:
- return SPECIAL_UNSIGNED_LT;
- case SPECIAL_NOTEQUAL:
- return op;
- case '>':
- case SPECIAL_GTE:
- return '>';
- case SPECIAL_UNSIGNED_GT:
- case SPECIAL_UNSIGNED_GTE:
- return SPECIAL_UNSIGNED_GT;
}
! return 0;
! case SPECIAL_GTE:
! switch (op) {
! case SPECIAL_LTE:
! return SPECIAL_EQUAL;
! case '>':
! case SPECIAL_GTE:
! case SPECIAL_EQUAL:
! return op;
! case SPECIAL_NOTEQUAL:
return '>';
}
! return 0;
! case '>':
! switch (op) {
! case '>':
! case SPECIAL_GTE:
! case SPECIAL_NOTEQUAL:
! return '>';
! }
! return 0;
! case SPECIAL_UNSIGNED_LT:
! switch (op) {
! case SPECIAL_UNSIGNED_LT:
! case SPECIAL_UNSIGNED_LTE:
! case SPECIAL_NOTEQUAL:
! return SPECIAL_UNSIGNED_LT;
! }
! return 0;
! case SPECIAL_UNSIGNED_LTE:
! switch (op) {
! case SPECIAL_UNSIGNED_LT:
! case SPECIAL_UNSIGNED_LTE:
! case SPECIAL_EQUAL:
! return op;
! case SPECIAL_NOTEQUAL:
! return SPECIAL_UNSIGNED_LT;
! case SPECIAL_UNSIGNED_GTE:
return SPECIAL_EQUAL;
! }
! return 0;
! case SPECIAL_UNSIGNED_GTE:
! switch (op) {
! case SPECIAL_UNSIGNED_LTE:
! return SPECIAL_EQUAL;
! case SPECIAL_NOTEQUAL:
! return SPECIAL_UNSIGNED_GT;
! case SPECIAL_EQUAL:
! case SPECIAL_UNSIGNED_GTE:
! case SPECIAL_UNSIGNED_GT:
! return op;
! }
! return 0;
! case SPECIAL_UNSIGNED_GT:
! switch (op) {
! case SPECIAL_UNSIGNED_GT:
! case SPECIAL_UNSIGNED_GTE:
! case SPECIAL_NOTEQUAL:
! return SPECIAL_UNSIGNED_GT;
! }
! return 0;
! }
! return 0;
}
! static void pre_merge_hook(struct sm_state *sm)
{
! struct compare_data *data = sm->state->data;
! int other;
if (!data)
return;
! other = get_comparison(data->left, data->right);
! if (!other)
return;
! set_state(compare_id, sm->name, NULL,
alloc_compare_state(data->left, data->left_var, data->left_vsl,
! other,
data->right, data->right_var, data->right_vsl));
}
struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
{
struct compare_data *data = s1->data;
int op;
op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
- if (op)
return alloc_compare_state(
data->left, data->left_var, data->left_vsl,
op,
data->right, data->right_var, data->right_vsl);
- return &undefined;
}
static struct smatch_state *alloc_link_state(struct string_list *links)
{
struct smatch_state *state;
--- 415,582 ----
if (GT == 2) {
if (EQ == 2)
return SPECIAL_GTE;
return '>';
}
! return UNKNOWN_COMPARISON;
}
! /*
! * This is mostly used when you know from extra state that a <= b but you
! * know from comparisons that a != b so then if take the intersection then
! * we know that a < b. The name is taken from the fact that the intersection
! * of < and <= is <.
! */
! int comparison_intersection(int left_compare, int right_compare)
{
! int LT, GT, EQ, NE, total;
! if (left_compare == IMPOSSIBLE_COMPARISON ||
! right_compare == IMPOSSIBLE_COMPARISON)
! return IMPOSSIBLE_COMPARISON;
! left_compare = remove_unsigned_from_comparison(left_compare);
! right_compare = remove_unsigned_from_comparison(right_compare);
!
! LT = GT = EQ = NE = total = 0;
!
! /* Only one side is known. */
! if (!left_compare)
! return right_compare;
! if (!right_compare)
! return left_compare;
!
! switch (left_compare) {
case '<':
! LT++;
! total += 1;
! break;
case SPECIAL_LTE:
+ LT++;
+ EQ++;
+ total += 2;
+ break;
+ case SPECIAL_EQUAL:
+ EQ++;
+ total += 1;
+ break;
case SPECIAL_NOTEQUAL:
! NE++;
! total += 1;
! break;
! case SPECIAL_GTE:
! GT++;
! EQ++;
! total += 2;
! break;
! case '>':
! GT++;
! total += 1;
! break;
! default:
! return UNKNOWN_COMPARISON;
}
!
! switch (right_compare) {
case '<':
+ LT++;
+ total += 1;
+ break;
case SPECIAL_LTE:
+ LT++;
+ EQ++;
+ total += 2;
+ break;
case SPECIAL_EQUAL:
! EQ++;
! total += 1;
! break;
case SPECIAL_NOTEQUAL:
! NE++;
! total += 1;
! break;
case SPECIAL_GTE:
! GT++;
! EQ++;
! total += 2;
! break;
! case '>':
! GT++;
! total += 1;
! break;
! default:
! return UNKNOWN_COMPARISON;
}
!
! if (LT == 2) {
! if (EQ == 2)
! return SPECIAL_LTE;
return '<';
}
!
! if (GT == 2) {
! if (EQ == 2)
! return SPECIAL_GTE;
return '>';
}
! if (EQ == 2)
return SPECIAL_EQUAL;
! if (total == 2 && EQ && NE)
! return IMPOSSIBLE_COMPARISON;
! if (GT && LT)
! return IMPOSSIBLE_COMPARISON;
! if (GT && NE)
! return '>';
! if (LT && NE)
! return '<';
! if (NE == 2)
! return SPECIAL_NOTEQUAL;
! if (total == 2 && (LT || GT) && EQ)
! return IMPOSSIBLE_COMPARISON;
!
! return UNKNOWN_COMPARISON;
}
! static void pre_merge_hook(struct sm_state *cur, struct sm_state *other)
{
! struct compare_data *data = cur->state->data;
! int extra, new;
! static bool in_recurse;
if (!data)
return;
!
! if (in_recurse)
return;
+ in_recurse = true;
+ extra = comparison_from_extra(data->left, data->right);
+ in_recurse = false;
+ if (!extra)
+ return;
+ new = comparison_intersection(extra, data->comparison);
+ if (new == data->comparison)
+ return;
! set_state(compare_id, cur->name, NULL,
alloc_compare_state(data->left, data->left_var, data->left_vsl,
! new,
data->right, data->right_var, data->right_vsl));
}
struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
{
struct compare_data *data = s1->data;
int op;
+ if (!data)
+ return &undefined;
+
op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
return alloc_compare_state(
data->left, data->left_var, data->left_vsl,
op,
data->right, data->right_var, data->right_vsl);
}
static struct smatch_state *alloc_link_state(struct string_list *links)
{
struct smatch_state *state;
*** 688,698 ****
flip ? SPECIAL_GTE : SPECIAL_LTE,
data->right, data->right_var, data->right_vsl);
set_state(compare_id, tmp, NULL, new);
break;
default:
! set_state(compare_id, tmp, NULL, &undefined);
}
} END_FOR_EACH_PTR(tmp);
}
static void match_dec(struct sm_state *sm, bool preserve)
--- 710,724 ----
flip ? SPECIAL_GTE : SPECIAL_LTE,
data->right, data->right_var, data->right_vsl);
set_state(compare_id, tmp, NULL, new);
break;
default:
! new = alloc_compare_state(
! data->left, data->left_var, data->left_vsl,
! UNKNOWN_COMPARISON,
! data->right, data->right_var, data->right_vsl);
! set_state(compare_id, tmp, NULL, new);
}
} END_FOR_EACH_PTR(tmp);
}
static void match_dec(struct sm_state *sm, bool preserve)
*** 702,722 ****
char *tmp;
links = sm->state->data;
FOR_EACH_PTR(links, tmp) {
state = get_state(compare_id, tmp, NULL);
switch (state_to_comparison(state)) {
case SPECIAL_EQUAL:
case SPECIAL_LTE:
case SPECIAL_UNSIGNED_LTE:
case '<':
case SPECIAL_UNSIGNED_LT: {
- struct compare_data *data = state->data;
- struct smatch_state *new;
-
if (preserve)
break;
new = alloc_compare_state(
data->left, data->left_var, data->left_vsl,
--- 728,752 ----
char *tmp;
links = sm->state->data;
FOR_EACH_PTR(links, tmp) {
+ struct compare_data *data;
+ struct smatch_state *new;
+
state = get_state(compare_id, tmp, NULL);
+ if (!state || !state->data)
+ continue;
+ data = state->data;
+
switch (state_to_comparison(state)) {
case SPECIAL_EQUAL:
case SPECIAL_LTE:
case SPECIAL_UNSIGNED_LTE:
case '<':
case SPECIAL_UNSIGNED_LT: {
if (preserve)
break;
new = alloc_compare_state(
data->left, data->left_var, data->left_vsl,
*** 724,734 ****
data->right, data->right_var, data->right_vsl);
set_state(compare_id, tmp, NULL, new);
break;
}
default:
! set_state(compare_id, tmp, NULL, &undefined);
}
} END_FOR_EACH_PTR(tmp);
}
static void reset_sm(struct sm_state *sm)
--- 754,768 ----
data->right, data->right_var, data->right_vsl);
set_state(compare_id, tmp, NULL, new);
break;
}
default:
! new = alloc_compare_state(
! data->left, data->left_var, data->left_vsl,
! UNKNOWN_COMPARISON,
! data->right, data->right_var, data->right_vsl);
! set_state(compare_id, tmp, NULL, new);
}
} END_FOR_EACH_PTR(tmp);
}
static void reset_sm(struct sm_state *sm)
*** 737,747 ****
char *tmp;
links = sm->state->data;
FOR_EACH_PTR(links, tmp) {
! set_state(compare_id, tmp, NULL, &undefined);
} END_FOR_EACH_PTR(tmp);
set_state(link_id, sm->name, sm->sym, &undefined);
}
static bool match_add_sub_assign(struct sm_state *sm, struct expression *expr)
--- 771,794 ----
char *tmp;
links = sm->state->data;
FOR_EACH_PTR(links, tmp) {
! struct smatch_state *old, *new;
!
! old = get_state(compare_id, tmp, NULL);
! if (!old || !old->data) {
! new = &undefined;
! } else {
! struct compare_data *data = old->data;
!
! new = alloc_compare_state(
! data->left, data->left_var, data->left_vsl,
! UNKNOWN_COMPARISON,
! data->right, data->right_var, data->right_vsl);
! }
! set_state(compare_id, tmp, NULL, new);
} END_FOR_EACH_PTR(tmp);
set_state(link_id, sm->name, sm->sym, &undefined);
}
static bool match_add_sub_assign(struct sm_state *sm, struct expression *expr)
*** 847,857 ****
if (!get_implied_rl(expr->unop, &left) ||
!get_implied_rl(parent->right, &right))
return;
op = rl_comparison(left, right);
! if (!op)
return;
add_comparison(expr->unop, op, parent->right);
}
--- 894,904 ----
if (!get_implied_rl(expr->unop, &left) ||
!get_implied_rl(parent->right, &right))
return;
op = rl_comparison(left, right);
! if (op == UNKNOWN_COMPARISON)
return;
add_comparison(expr->unop, op, parent->right);
}
*** 1014,1025 ****
orig_comparison = get_orig_comparison(pre_stree, left_var, right_var);
true_comparison = combine_comparisons(left_comparison, right_comparison);
false_comparison = combine_comparisons(left_false_comparison, right_comparison);
! true_comparison = filter_comparison(orig_comparison, true_comparison);
! false_comparison = filter_comparison(orig_comparison, false_comparison);
if (strcmp(left_var, right_var) > 0) {
struct expression *tmp_expr = left_expr;
const char *tmp_var = left_var;
struct var_sym_list *tmp_vsl = left_vsl;
--- 1061,1072 ----
orig_comparison = get_orig_comparison(pre_stree, left_var, right_var);
true_comparison = combine_comparisons(left_comparison, right_comparison);
false_comparison = combine_comparisons(left_false_comparison, right_comparison);
! true_comparison = comparison_intersection(orig_comparison, true_comparison);
! false_comparison = comparison_intersection(orig_comparison, false_comparison);
if (strcmp(left_var, right_var) > 0) {
struct expression *tmp_expr = left_expr;
const char *tmp_var = left_var;
struct var_sym_list *tmp_vsl = left_vsl;
*** 1274,1285 ****
op = flip_comparison(op);
false_op = flip_comparison(false_op);
}
orig_comparison = get_comparison(left_expr, right_expr);
! op = filter_comparison(orig_comparison, op);
! false_op = filter_comparison(orig_comparison, false_op);
snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
true_state = alloc_compare_state(
left_expr, left, left_vsl,
op,
--- 1321,1332 ----
op = flip_comparison(op);
false_op = flip_comparison(false_op);
}
orig_comparison = get_comparison(left_expr, right_expr);
! op = comparison_intersection(orig_comparison, op);
! false_op = comparison_intersection(orig_comparison, false_op);
snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
true_state = alloc_compare_state(
left_expr, left, left_vsl,
op,
*** 1332,1342 ****
new_left = left->right;
new_right = binop_expression(right, '-', left->left);
handle_comparison(new_left, expr->op, new_right, NULL, NULL);
}
-
redo = 0;
left = strip_parens(expr->left);
right = strip_parens(expr->right);
if (get_last_expr_from_expression_stmt(expr->left)) {
left = get_last_expr_from_expression_stmt(expr->left);
--- 1379,1388 ----
*** 1616,1626 ****
struct smatch_state *state;
int invert = 0;
int ret = 0;
if (!one || !two)
! return 0;
if (strcmp(one, two) == 0)
return SPECIAL_EQUAL;
if (strcmp(one, two) > 0) {
--- 1662,1672 ----
struct smatch_state *state;
int invert = 0;
int ret = 0;
if (!one || !two)
! return UNKNOWN_COMPARISON;
if (strcmp(one, two) == 0)
return SPECIAL_EQUAL;
if (strcmp(one, two) > 0) {
*** 1644,1657 ****
static int get_comparison_helper(struct expression *a, struct expression *b, bool use_extra)
{
char *one = NULL;
char *two = NULL;
! int ret = 0;
! if (!a || !b)
! return 0;
a = strip_parens(a);
b = strip_parens(b);
move_plus_to_minus(&a, &b);
--- 1690,1705 ----
static int get_comparison_helper(struct expression *a, struct expression *b, bool use_extra)
{
char *one = NULL;
char *two = NULL;
! int ret = UNKNOWN_COMPARISON;
! int extra = UNKNOWN_COMPARISON;
! if (a == UNKNOWN_COMPARISON ||
! b == UNKNOWN_COMPARISON)
! return UNKNOWN_COMPARISON;
a = strip_parens(a);
b = strip_parens(b);
move_plus_to_minus(&a, &b);
*** 1675,1701 ****
free_string(two);
two = chunk_to_var(b->left);
ret = get_comparison_strings(one, two);
}
! if (!ret)
goto free;
if ((is_plus_one(a) || is_minus_one(b)) && ret == '<')
ret = SPECIAL_LTE;
else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>')
ret = SPECIAL_GTE;
else
! ret = 0;
free:
free_string(one);
free_string(two);
! if (!ret && use_extra)
! return comparison_from_extra(a, b);
! return ret;
}
int get_comparison(struct expression *a, struct expression *b)
{
return get_comparison_helper(a, b, true);
--- 1723,1748 ----
free_string(two);
two = chunk_to_var(b->left);
ret = get_comparison_strings(one, two);
}
! if (ret == UNKNOWN_COMPARISON)
goto free;
if ((is_plus_one(a) || is_minus_one(b)) && ret == '<')
ret = SPECIAL_LTE;
else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>')
ret = SPECIAL_GTE;
else
! ret = UNKNOWN_COMPARISON;
free:
free_string(one);
free_string(two);
! extra = comparison_from_extra(a, b);
! return comparison_intersection(ret, extra);
}
int get_comparison(struct expression *a, struct expression *b)
{
return get_comparison_helper(a, b, true);
*** 1903,1917 ****
void __add_return_comparison(struct expression *call, const char *range)
{
struct expression *arg;
int comparison;
! char buf[4];
if (!str_to_comparison_arg(range, call, &comparison, &arg))
return;
! snprintf(buf, sizeof(buf), "%s", show_special(comparison));
update_links_from_call(call, comparison, arg);
add_comparison(call, comparison, arg);
}
void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
--- 1950,1964 ----
void __add_return_comparison(struct expression *call, const char *range)
{
struct expression *arg;
int comparison;
! char buf[16];
if (!str_to_comparison_arg(range, call, &comparison, &arg))
return;
! snprintf(buf, sizeof(buf), "%s", show_comparison(comparison));
update_links_from_call(call, comparison, arg);
add_comparison(call, comparison, arg);
}
void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
*** 1969,1983 ****
continue;
if (!param->ident)
continue;
snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
compare = get_comparison_strings(var, buf);
! if (!compare)
continue;
! if (show_special(compare)[0] != starts_with)
continue;
! snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
ret_str = alloc_sname(buf);
break;
} END_FOR_EACH_PTR(param);
free_string(var);
--- 2016,2031 ----
continue;
if (!param->ident)
continue;
snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
compare = get_comparison_strings(var, buf);
! if (compare == UNKNOWN_COMPARISON ||
! compare == IMPOSSIBLE_COMPARISON)
continue;
! if (show_comparison(compare)[0] != starts_with)
continue;
! snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
ret_str = alloc_sname(buf);
break;
} END_FOR_EACH_PTR(param);
free_string(var);
*** 2004,2016 ****
i++;
if (!param->ident)
continue;
snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
compare = get_comparison_strings(name, buf);
! if (!compare)
continue;
! snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
return alloc_sname(buf);
} END_FOR_EACH_PTR(param);
return NULL;
}
--- 2052,2065 ----
i++;
if (!param->ident)
continue;
snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
compare = get_comparison_strings(name, buf);
! if (compare == UNKNOWN_COMPARISON ||
! compare == IMPOSSIBLE_COMPARISON)
continue;
! snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
return alloc_sname(buf);
} END_FOR_EACH_PTR(param);
return NULL;
}
*** 2047,2057 ****
continue;
snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
compare = get_comparison_strings(var, buf);
if (!compare)
continue;
! snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
ret_str = alloc_sname(buf);
break;
} END_FOR_EACH_PTR(param);
free:
--- 2096,2106 ----
continue;
snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
compare = get_comparison_strings(var, buf);
if (!compare)
continue;
! snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
ret_str = alloc_sname(buf);
break;
} END_FOR_EACH_PTR(param);
free:
*** 2126,2136 ****
continue;
sm = get_sm_state(compare_id, link, NULL);
if (!sm)
continue;
data = sm->state->data;
! if (!data || !data->comparison)
continue;
arg_name = expr_to_var(arg);
if (!arg_name)
continue;
--- 2175,2187 ----
continue;
sm = get_sm_state(compare_id, link, NULL);
if (!sm)
continue;
data = sm->state->data;
! if (!data ||
! data->comparison == UNKNOWN_COMPARISON ||
! data->comparison == IMPOSSIBLE_COMPARISON)
continue;
arg_name = expr_to_var(arg);
if (!arg_name)
continue;
*** 2151,2161 ****
if (strcmp(right_vs->var, right_name) != 0)
goto free;
right_name = get_printed_param_name(expr, right_vs->var, right_vs->sym);
if (!right_name)
goto free;
! snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(comparison), right_name);
sql_insert_caller_info(expr, PARAM_COMPARE, i, "$", info_buf);
free:
free_string(arg_name);
} END_FOR_EACH_PTR(link);
--- 2202,2212 ----
if (strcmp(right_vs->var, right_name) != 0)
goto free;
right_name = get_printed_param_name(expr, right_vs->var, right_vs->sym);
if (!right_name)
goto free;
! snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(comparison), right_name);
sql_insert_caller_info(expr, PARAM_COMPARE, i, "$", info_buf);
free:
free_string(arg_name);
} END_FOR_EACH_PTR(link);
*** 2201,2211 ****
continue;
right_name = get_printed_param_name(call, right->var, right->sym);
if (!right_name)
continue;
! snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(data->comparison), right_name);
sql_insert_caller_info(call, PARAM_COMPARE, param, printed_name, info_buf);
} END_FOR_EACH_PTR(link);
}
static void print_return_value_comparison(int return_id, char *return_ranges, struct expression *expr)
--- 2252,2262 ----
continue;
right_name = get_printed_param_name(call, right->var, right->sym);
if (!right_name)
continue;
! snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(data->comparison), right_name);
sql_insert_caller_info(call, PARAM_COMPARE, param, printed_name, info_buf);
} END_FOR_EACH_PTR(link);
}
static void print_return_value_comparison(int return_id, char *return_ranges, struct expression *expr)
*** 2272,2282 ****
FOR_EACH_PTR(links, link) {
sm = get_sm_state(compare_id, link, NULL);
if (!sm)
continue;
data = sm->state->data;
! if (!data || !data->comparison)
continue;
if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
continue;
left = first_ptr_list((struct ptr_list *)data->left_vsl);
--- 2323,2335 ----
FOR_EACH_PTR(links, link) {
sm = get_sm_state(compare_id, link, NULL);
if (!sm)
continue;
data = sm->state->data;
! if (!data ||
! data->comparison == UNKNOWN_COMPARISON ||
! data->comparison == IMPOSSIBLE_COMPARISON)
continue;
if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
continue;
left = first_ptr_list((struct ptr_list *)data->left_vsl);
*** 2314,2324 ****
* FIXME: this should reject $ type variables (as
* opposed to $->foo type). Those should come from
* smatch_param_compare_limit.c.
*/
! snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(data->comparison), right_buf);
sql_insert_return_states(return_id, return_ranges,
PARAM_COMPARE, left_param, left_buf, info_buf);
} END_FOR_EACH_PTR(link);
} END_FOR_EACH_SM(tmp);
--- 2367,2377 ----
* FIXME: this should reject $ type variables (as
* opposed to $->foo type). Those should come from
* smatch_param_compare_limit.c.
*/
! snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(data->comparison), right_buf);
sql_insert_return_states(return_id, return_ranges,
PARAM_COMPARE, left_param, left_buf, info_buf);
} END_FOR_EACH_PTR(link);
} END_FOR_EACH_SM(tmp);
*** 2491,2501 ****
goto free;
state_op = state_to_comparison(state);
if (!state_op)
goto free;
! if (!filter_comparison(remove_unsigned_from_comparison(state_op), op))
ret = 1;
free:
free_string(left_name);
free_string(right_name);
return ret;
--- 2544,2554 ----
goto free;
state_op = state_to_comparison(state);
if (!state_op)
goto free;
! if (!comparison_intersection(remove_unsigned_from_comparison(state_op), op))
ret = 1;
free:
free_string(left_name);
free_string(right_name);
return ret;
*** 2589,2629 ****
static void filter_by_sm(struct sm_state *sm, int op,
struct state_list **true_stack,
struct state_list **false_stack)
{
struct compare_data *data;
! int istrue = 0;
! int isfalse = 0;
if (!sm)
return;
data = sm->state->data;
! if (!data) {
! if (sm->merged) {
! filter_by_sm(sm->left, op, true_stack, false_stack);
! filter_by_sm(sm->right, op, true_stack, false_stack);
! }
return;
- }
! if (data->comparison &&
! data->comparison == filter_comparison(data->comparison, op))
! istrue = 1;
! if (data->comparison &&
! data->comparison == filter_comparison(data->comparison, negate_comparison(op)))
! isfalse = 1;
! if (istrue)
add_ptr_list(true_stack, sm);
! if (isfalse)
add_ptr_list(false_stack, sm);
!
! if (sm->merged) {
filter_by_sm(sm->left, op, true_stack, false_stack);
filter_by_sm(sm->right, op, true_stack, false_stack);
- }
}
struct sm_state *comparison_implication_hook(struct expression *expr,
struct state_list **true_stack,
struct state_list **false_stack)
--- 2642,2692 ----
static void filter_by_sm(struct sm_state *sm, int op,
struct state_list **true_stack,
struct state_list **false_stack)
{
struct compare_data *data;
! int is_true = 0;
! int is_false = 0;
if (!sm)
return;
data = sm->state->data;
! if (!data || data->comparison == UNKNOWN_COMPARISON)
! goto split;
! if (data->comparison == IMPOSSIBLE_COMPARISON)
return;
! /*
! * We want to check that "data->comparison" is totally inside "op". So
! * if data->comparison is < and op is <= then that's true. Or if
! * data->comparison is == and op is <= then that's true. But if
! * data->comparison is <= and op is < than that's neither true nor
! * false.
! */
! if (data->comparison == comparison_intersection(data->comparison, op))
! is_true = 1;
! if (data->comparison == comparison_intersection(data->comparison, negate_comparison(op)))
! is_false = 1;
! if (debug_implied()) {
! sm_msg("%s: %s: op = '%s' negated '%s'. true_intersect = '%s' false_insersect = '%s' sm = '%s'",
! __func__,
! sm->state->name,
! alloc_sname(show_comparison(op)),
! alloc_sname(show_comparison(negate_comparison(op))),
! alloc_sname(show_comparison(comparison_intersection(data->comparison, op))),
! alloc_sname(show_comparison(comparison_intersection(data->comparison, negate_comparison(op)))),
! show_sm(sm));
! }
! if (is_true)
add_ptr_list(true_stack, sm);
! if (is_false)
add_ptr_list(false_stack, sm);
! split:
filter_by_sm(sm->left, op, true_stack, false_stack);
filter_by_sm(sm->right, op, true_stack, false_stack);
}
struct sm_state *comparison_implication_hook(struct expression *expr,
struct state_list **true_stack,
struct state_list **false_stack)
*** 2663,2672 ****
filter_by_sm(sm, op, true_stack, false_stack);
if (!*true_stack && !*false_stack)
return NULL;
! if (option_debug)
sm_msg("implications from comparison: (%s)", show_sm(sm));
return sm;
}
--- 2726,2735 ----
filter_by_sm(sm, op, true_stack, false_stack);
if (!*true_stack && !*false_stack)
return NULL;
! if (debug_implied())
sm_msg("implications from comparison: (%s)", show_sm(sm));
return sm;
}