RedundantIfForBooleanCheck makes invalid suggestion

[Luro02]

Summary

The two expressions are equivalent, except for the case where ìsSafe = true, isEdgeLegal = true, isEdgeSafe = false.

Lint Name

RedundantIfForBooleanCheck

Reproducer

public static boolean edgeCondition(boolean isSafe, boolean isEdgeLegal, boolean isEdgeSafe) {
    if (isSafe) {
        return isEdgeLegal && isEdgeSafe;
    }

    return isEdgeLegal;
}

Given the above code, it suggests:

return isSafe && (isEdgeLegal && isEdgeSafe) || isEdgeLegal;

This is wrong.

The assumption is that the boolean isSafe is false when the || isEdgeLegal is evaluated. This is not the case, therefore an !isSafe && must be added to the suggestion:

return isSafe && (isEdgeLegal && isEdgeSafe) || !isSafe && isEdgeLegal;

[Luro02]

Why didn't I notice this issue?

For the past few days, I have been wondering why I never noticed this major problem with the suggestion. I should have noticed such a big problem.

My guess is that this happened when I started expanding the check. In the beginning it only checked the return true/return false cases and later it was expanded to the "any boolean expression in return".

Given this generalized code:

if (a) {
  return b;
} else {
  return c;
}

The code notices that the result should be either a && b or !a && c.

When the value b is a boolean literal like b = true, the expression a && b || !a && c -> a && true || !a && c -> a || !a && c
and the last one is the classic case in boolean algebra called "Absorption Property":

A + AB = A
A(A + B) = A // (this is technically implied by the former and a few boolean transformations)

I assumed these simplifications would hold for any expression and not just literals, resulting in the wrong suggestion.

Why is the above important and I don't just fix the bug?

Well, I want to fix it correctly and maybe improve the whole code while doing this. Given this check covers so much code, I don't want to suggest things like

This code could be simplified to 'return a || !a && b'

Which are technically true, but these suggestions are unnecessarily verbose, because it could just as well be

This code could be simplified to 'return a || b'

and to do this correctly, I need to know when I can emit which.

Refactor the simple literal case into a separate problem type?

There were talks that the check suggests things that aren't much simpler, especially when the code doesn't have simple literals. The underlying issue are very complex boolean expressions, and in my opinion that is not the fault of the autograder. Either way, by separating the "everyone agrees that is wrong" from the "maybe this shouldn't subtract points", it will allow more control in the future.

How will this be implemented?

There are two options:

1. Special case the code to emit the simpler form when applicable or the explicit one when not (might be error-prone
2. Introduce code that simplifies the representations. The core structure (namely the Fold interface) is already there. Main benefit would be that this can then be used to finally introduce a check that can detect unnecessarily complicated boolean expressions.

I am inclined towards option 2, because the check to simplify boolean expressions will inevitably be implemented in the future, and other checks can benefit from this.

For preserving the original expressions (kinda important so people know why the code can be simplified/what they are expected to do), I would likely make this convert the actual code into a simpler form like the above with a, b, c that is then later mapped to the actual code.

In addition to that, it can then

• remove double negations
• stuff like !(==) -> !=
• and more