[RFC PATCH 0/2] check for identical exprs on LHS and RHS of '&&'

[RFC PATCH 0/2] check for identical exprs on LHS and RHS of '&&'

[Chris Forbes]

Hi, I've started working on a new check for sparse to pick up a common 
error -- identical expressions appearing on both sides of some binary
operators.

This initially supports '&&', and incompletely -- but the plan is to
check instances of '!=', '==' and '||' the same way.

The check relies on recursively walking the ->left and ->right expressions, 
looking for differences. The implementation is a little verbose, but can 
be shared between all the operators.

What I'd like to know is:

* Do people consider this a worthwhile check to make?
* Am I "doing it right" with the expression walking?
* Are there other cases which people would be interested in?

Cheers

-- Chris

[PATCH 1/2] add test case for identical exprs on LHS and RHS of '&&' operator

[Chris Forbes]

---
 validation/check_identical_exprs_on_and.c |   24 ++++++++++++++++++++++++
 1 files changed, 24 insertions(+), 0 deletions(-)
 create mode 100644 validation/check_identical_exprs_on_and.c

diff --git a/validation/check_identical_exprs_on_and.c b/validation/check_identical_exprs_on_and.c
new file mode 100644
index 0000000..712395d
--- /dev/null
+++ b/validation/check_identical_exprs_on_and.c
@@ -0,0 +1,24 @@
+extern void bar(void);
+
+static void foo(void *a, void *b, void *c)
+{
+	if (a && a)	/* should warn */
+		bar();
+
+	if (a && b)	/* should not warn */
+		bar();
+
+	if ((a == b) && (a == b))	/* should warn */
+		bar();
+
+	if ((a == b) && (b == c))	/* should not warn */
+		bar();
+}
+/*
+ * check-name: A warning should be issued for identical expressions on both sides of the '&&' operator.
+ *
+ * check-error-start
+check_identical_exprs_on_and.c:5:15: warning: identical expressions on both sides of '&&'
+check_identical_exprs_on_and.c:11:22: warning: identical expressions on both sides of '&&'
+ * check-error-end
+ */
-- 
1.7.4.1

[PATCH 2/2] initial work on check for identical exprs on both sides of '&&'; needs more

[Chris Forbes]

---
 evaluate.c |   59 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 59 insertions(+), 0 deletions(-)

diff --git a/evaluate.c b/evaluate.c
index f8343c2..af0be59 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -853,8 +853,67 @@ static struct symbol *evaluate_conditional(struct expression *expr, int iterator
 	return ctype;
 }
 
+static int are_equivalent_expr(struct expression *lhs, struct expression *rhs)
+{
+	/* recursively determine if lhs ~ rhs. */
+	if (!lhs ^ !rhs) return 0;
+
+	if (lhs->type != rhs->type) return 0;
+	if (lhs->flags != rhs->flags) return 0;
+	if (lhs->op != rhs->op) return 0;
+	if (lhs->ctype != rhs->ctype) return 0;
+
+	switch( lhs->type ) {
+	case EXPR_VALUE:
+		if (lhs->value != rhs->value) return 0;
+		if (lhs->taint != rhs->taint) return 0;
+		break;
+	case EXPR_FVALUE:
+		if (lhs->fvalue != rhs->fvalue) return 0;
+		break;
+	case EXPR_STRING:
+		if (lhs->wide != rhs->wide) return 0;
+		if (lhs->string->length != rhs->string->length) return 0;
+		if (memcmp(lhs->string->data, rhs->string->data,
+			lhs->string->length)) return 0;
+		break;
+/*	case EXPR_UNOP:	*/	/* this is mentioned in the union, but doesn't
+				actually exist */
+	case EXPR_PREOP:
+	case EXPR_POSTOP:
+		if (!are_equivalent_expr(lhs->unop, rhs->unop)) return 0;
+		if (lhs->op_value != rhs->op_value) return 0;
+		break;
+	case EXPR_SYMBOL:
+	case EXPR_TYPE:
+		if (lhs->symbol != rhs->symbol) return 0;
+		break;
+	case EXPR_BINOP:
+	case EXPR_COMMA:
+	case EXPR_COMPARE:
+	case EXPR_LOGICAL:
+	case EXPR_ASSIGNMENT:
+		if (!are_equivalent_expr(lhs->left, rhs->left)) return 0;
+		if (!are_equivalent_expr(lhs->right, rhs->right)) return 0;
+		break;
+
+		/* blah, more... */
+
+	default:
+		return 0;
+	}
+
+	return 1;
+}
+
 static struct symbol *evaluate_logical(struct expression *expr)
 {
+	if (expr->op == SPECIAL_LOGICAL_AND &&
+		are_equivalent_expr(expr->left, expr->right)) {
+		warning(expr->pos, "identical expressions on both "
+			"sides of '&&'");
+	}
+
 	if (!evaluate_conditional(expr->left, 0))
 		return NULL;
 	if (!evaluate_conditional(expr->right, 0))
-- 
1.7.4.1

Re: [RFC PATCH 0/2] check for identical exprs on LHS and RHS of '&&'

[Josh Triplett]

On Wed, Aug 10, 2011 at 09:07:13PM +1200, Chris Forbes wrote:
> Hi, I've started working on a new check for sparse to pick up a common 
> error -- identical expressions appearing on both sides of some binary
> operators.
> 
> This initially supports '&&', and incompletely -- but the plan is to
> check instances of '!=', '==' and '||' the same way.
> 
> The check relies on recursively walking the ->left and ->right expressions, 
> looking for differences. The implementation is a little verbose, but can 
> be shared between all the operators.
> 
> What I'd like to know is:
> 
> * Do people consider this a worthwhile check to make?

I'd definitely love to see this check.  I saw an example of the kinds of
bugs it can find in a recent article
(http://software.intel.com/en-us/blogs/2011/08/08/pvs-studio-vs-clang/),
and immediately wished Sparse and/or GCC would include that check.

> * Am I "doing it right" with the expression walking?

Seems OK at first glance, with one exception: you need to handle
expressions with side-effects specially, since you could legitimately
write something like (x == func() && x == func()), or (x == *p++ && x ==
*p++).

> * Are there other cases which people would be interested in?

How about checking for the same expression multiple times in a single
block of | or & expressions?  (flag1 | flag2 | flag2) seems like a
likely copy/paste error.

- Josh Triplett

Re: [RFC PATCH 0/2] check for identical exprs on LHS and RHS of '&&'

[Al Viro]

On Wed, Aug 10, 2011 at 10:44:23AM -0700, Josh Triplett wrote:

> How about checking for the same expression multiple times in a single
> block of | or & expressions?  (flag1 | flag2 | flag2) seems like a
> likely copy/paste error.

... or result of macro expansion.

Re: [RFC PATCH 0/2] check for identical exprs on LHS and RHS of '&&'

[Christopher Li]

On Wed, Aug 10, 2011 at 2:07 AM, Chris Forbes <chrisf@ijw.co.nz> wrote:
> * Do people consider this a worthwhile check to make?
> * Am I "doing it right" with the expression walking?
> * Are there other cases which people would be interested in?

To evaluate a particular check, it is useful to look at the out come of the
check, and how complex it is the change.

e.g. How many the error caught by this check on some open source
projects. And how high is the false positive.

The expression walking is on the right track.

Chris

Re: [RFC PATCH 0/2] check for identical exprs on LHS and RHS of '&&'

[Dan Carpenter]

On Wed, Aug 10, 2011 at 06:46:15PM +0100, Al Viro wrote:
> On Wed, Aug 10, 2011 at 10:44:23AM -0700, Josh Triplett wrote:
> 
> > How about checking for the same expression multiple times in a single
> > block of | or & expressions?  (flag1 | flag2 | flag2) seems like a
> > likely copy/paste error.
> 
> ... or result of macro expansion.

In Smatch, we store where all the macros are when we run the
preprocessor.  Then for some checks we check if there was a macro at
&expr->pos to see if it's inside a macro, and if so then the error is
suppressed.

For example, Smatch prints an error if you dereference a variable and
then later check it for NULL.  But if the check is inside a macro the
error gets suppressed.

    foo->bar;
    if (foo) { ...  <-- most likely an error.

    foo->bar;
    some_macro_that_checks_for_null(foo);  <-- not an error.

regards,
dan carpenter