#111 Rules to catch redundancies

[Luke Francl]

Tom,

You probably saw the research paper by Dawson Engler
that was on Slashdot lately. "Using Redundancies to
Find Errors": http://www.stanford.edu/~engler/p401-xie.pdf

Engler found that redundancies, such as assigning a
value to to the same local variable very close together
or assigning a variable to itself are often indicators
of serious errors in code.

There were four types of redundancies that Engler's
tool checked for:

1. Idempotent operations (example: x = x )
2. Redundant assignments (variables assigned but never
   used, variables assigned to a non-constant that is then
   overwritten without being read, variables assigned to a
   constant that is then overwritten without being read
   (often defensive programming))
3. Dead code (code which is logically impossible to
   execute)
4. Redundant conditionals (similar to dead code,
   conditionals which cannot be reached)

At the end of the paper, Engler mentions that
implementing these kinds of checks in a static code
analyser are hard if not impossible, so we probably
can't have all of this in PMD. But #1 should be easy
and we already have #2.

Anyway, thought you might be interested in this paper
and trying out some of Engler's techinques in PMD.

Luke

[Tom Copeland]

Logged In: YES
user_id=5159

Hi Luke -

Thanks very much. Let's see:

1 - yup, should be doable

2 - tricky, but doable. Some of these already have feature

requests in for them - i.e., Unused Assignment -
http://sourceforge.net/tracker/index.php?func=detail&aid=604240&group_id=56262&atid=479924.

3 and # 4 - I agree, could be quite tricky. But maybe we

could get some of the cases, i.e.:

if (x>0 && x > 1) {

}

although I'm not even sure how to do the expression analysis
to figure that one out.

Thanks for the thoughtful note,

tom

[Tom Copeland]

Logged In: YES
user_id=5159

Thinking about the idempotent operations some more. We
could catch:

public class Foo {
private int baz;
public void bar() {
int x = 2;
x = x; // yup
Buz b = new Buz();
b.x = b.x; // yup
this.baz = baz; // yup, but not if there's a parameter "baz"
}
}

Are there other examples of case #1? I skimmed the article;
I'll have to read it again...

Tom

[Luke Francl]

Logged In: YES
user_id=379782

That's looking good, but it's not quite all the cases.
The paper gives 4 cases:

1) variable assigned to itself (these are the ones you've
got in your example below)
2) divided by itself (x/x)
3) bitwise or'd with itself (x | x)
4) bitwise and' with itself (x & x)

Granted, these last 3 cases are as widespread.

These operations are listed in the first paragraph of
section 2 of the paper.

Luke

[Luke Francl]

Logged In: YES
user_id=379782

Err, that last message should read "these last three cases
aren't as widespread"

Luke

[Tom Copeland]

Logged In: YES
user_id=5159

Gotcha, thanks.

This would be a cool rule name,
too: "AvoidIdempotentOperations".

Tom

[C. Lamont Gilbert]

Logged In: YES
user_id=280374

3 and 4 are cought by the compiler.

I dont like defensive programming. it seems to mask possible
errors that the compiler would otherwise catch.

x/x != x, so that is not idempotent when assigned to x, but
is rather useless.

[Luke Francl]

Logged In: YES
user_id=379782

3 and 4 are caught by the compiler, but optomized away. What
Engler did is write a meta-compiler which warns you about
these things instead of ignoring them. He found that these
warnings were highly correlated to serious errors in the
program.

x/x is useless, which is why Engler flags it. I can't really
think of a reason a programmer would want to do that.

And that's really what this is about. Engler's work finds
code that no sane programmer would execute and warns you
about it.

[C. Lamont Gilbert]

Logged In: YES
user_id=280374

3 and 4 are not optimized away in my experience. The
compiler will refuse to compile the class. put a return 1/2
way down a method, and see what the compiler says about it.

I would suggest we focus on 1 and 2 where PMD could add value.

[Luke Francl]

Logged In: YES
user_id=379782

I'll take your word for it. I don't know for sure.

But your conclusion is correct: 1 and 2 are were PMD needs
to focus, because 3 and 4 are pretty out of scope for PMD.
If it did those things, I don't think it would be a static
code analyizer anymore...

[Tom Copeland]

Logged In: YES
user_id=5159

Fiddling with this a bit...

tom

[Tom Copeland]

Logged In: YES
user_id=5159

Hm, can't seem to get an XPath expression working. Closest
I got was:

//StatementExpression
[
AssignmentOperator[position() = 1]
and
PrimaryExpression/PrimaryPrefix/Name[@Image]
=
Expression/ConditionalAndExpression/InstanceOfExpression/PrimaryExpression/PrimaryPrefix/Name[@Image]
]

[Tom Copeland]

Logged In: YES
user_id=5159

Tricky, because you've got to check for stuff like:

i = -i;

and

x[5] = x[6];

[Tom Copeland]

Logged In: YES
user_id=5159

I've done some work on this and checked it in as the
IdempotentOperatonsRule.

tom

[Tom Copeland]

Logged In: YES
user_id=5159

Hm, I'm not sure if this is doable given the current state
of PMD. To avoid getting false positives on things like:

x[0]=x[1];

you have to figure out the type of both lhs and rhs operands.

Tom

[Tom Copeland]

Logged In: YES
user_id=5159

IdempotentOperationsRule is in CVS now.... comments are
welcome...

Yours,

Tom