boolean expression simplification/finding expressions that are always/never true

[Luro02]

What it does

There are strategies to simplify boolean expressions, by

• eliminating redundant variables
• redundant conditions
• detecting conditions that are always true or always false

One could write a check that is able to detect that.
There is nothing like that implemented at the moment, maybe the check that suggests simplifying !(a == b) -> a != b.

Some questions about this:

1. Does this happen frequently enough? I can't remember seeing this in a submission
2. Is it obvious enough that is justifies an annotation that might even subtract points?

Lint Name

No response

Category

No response

Example

<code>

Could be written as:

<code>

[Luro02]

For simplification, what can be simplified?

1. !(a == b) -> a != b
2. !(a ^ b) -> a == b
3. -> (a ^ b -> a != b) IMPORTANT: Check that variable type is boolean, otherwise the xor might not be equivalent
4. a && b || !a -> !a || b, similarly for a && b && c || !a which can be !a || b && c
5. Any boolean operation with a literal, like a == true or a && true
6. Comparisons like a > 1 && a > 2 -> a > 2. Here is another one: a > b && b > c || a <= b -> a <= b || b > c or a > b && b > c && b > 0 || (b > c) -> b > c

Things to account for:

• some of the simplifications are already implemented through dedicated checks
• introduce some form of measurement to decide if an expression is simpler than the original one. For example, one could measure the number of variables, the number of binary operators or the overall code size
• some expressions might have side-effects, preventing some things like reordering. It might be necessary to introduce a helper function like ExpressionUtil.hasNoSideEffects(expression). Problem here would be that this is a lot of work to do right.