This is an archive of the discontinued LLVM Phabricator instance.

[clang-tidy] Simplify boolean expressions by DeMorgan's theorem
AbandonedPublic

Authored by LegalizeAdulthood on Apr 28 2022, 5:29 PM.

Details

Summary

Make the following simplifications of boolean expressions:

!(!a ||  b) => ( a && !b)
!( a || !b) => (!a && b)
!(!a || !b) => ( a && b)
!(!a &&  b) => ( a || !b)
!( a && !b) => (!a || b)
!(!a && !b) => ( a || b)

Fixes #55092

Diff Detail

Event Timeline

LegalizeAdulthood requested review of this revision.Apr 28 2022, 5:29 PM

General question:

There is the question of whether or not the replacement should have ()s around the whole
thing because we don't analyze the context to see if the change in precedence between
operator! and operator&& or operator|| makes any difference.

Eugene.Zelenko added inline comments.
clang-tools-extra/docs/ReleaseNotes.rst
139

Please use alphabetical order for such entries.

LegalizeAdulthood marked an inline comment as done.

Sort changes by check name in docs

General question:

There is the question of whether or not the replacement should have ()s around the whole
thing because we don't analyze the context to see if the change in precedence between
operator! and operator&& or operator|| makes any difference.

I suppose it's better to be safe than sorry, so I'll update the check to surround the replacement
with parens.

Surround replacements with parens

LegalizeAdulthood edited the summary of this revision. (Show Details)Apr 29 2022, 2:09 PM
njames93 added inline comments.May 1 2022, 3:02 AM
clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp
586

This whole implementation would be alot simpler(and likely faster) if you matched on the generic case then in the check callback work out what replacement you need.

Finder->addMatcher(
    unaryOperator(
        Not,
        hasUnaryOperand(binaryOperator(
            hasAnyOperatorName("&&", "||"),
            hasEitherOperand(unaryOperator(Not))))).bind(Demorgan),
    this);
598–599

Maybe I'm overthinking this, but how come you don't need the match on the ParenExpr?
Is there some traversal mode?

clang-tools-extra/docs/ReleaseNotes.rst
139

@LegalizeAdulthood I've pushed the change to alphabetize the list in rG8a9e2dd48d81 seperately, please rebase.

njames93 added inline comments.May 1 2022, 9:22 AM
clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp
586

Come to think of it, you wouldn't even need to work out which. Just remove the outer !, Exchange || with && and invert each side of the binary operator.

Testing on VTK revealed this change:

-  this->SliceMapper->SetBackground((this->Background &&
-    !(this->SliceFacesCamera && this->InternalResampleToScreenPixels &&
-      !this->SeparateWindowLevelOperation)));
+  this->SliceMapper->SetBackground(
+      (this->Background &&
+       (!this->SliceFacesCamera && this->InternalResampleToScreenPixels ||
+        this->SeparateWindowLevelOperation)));

Which is incorrect. So more improvement is needed for the case of !(x && y && !z) or !(x || y || !z) is encountered.

clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp
586

These are good ideas, I'll take a look. I wasn't aware of hasEitherOperand. I mean, it's in that giant AST matcher reference page, but somehow I overlooked it. On Windows, we don't have TAB completion in clang-query either, so it becomes more difficult to interactively explore possibilities.

I also noticed that some of the simplifications being performed resulted in !(x || !y) coming out of other parts of the simplifier, so it should be the case that running this check on your code should result in no further changes to your code if you run the check again.

LegalizeAdulthood marked an inline comment as done.May 1 2022, 1:56 PM
LegalizeAdulthood added inline comments.
clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp
598–599

How can you have a binaryOperator as the child of unaryOperator without parens? The precedence doesn't allow it otherwise.

njames93 added inline comments.May 1 2022, 10:05 PM
clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp
598–599

Its more the point that the AST has the ParenExpr

!(a || !b);
`-UnaryOperator <col:12, col:21> 'bool' prefix '!' cannot overflow
  `-ParenExpr <col:13, col:21> 'bool'
    `-BinaryOperator <col:14, col:20> 'bool' '||'
      |-ImplicitCastExpr <col:14> 'bool' <LValueToRValue>
      | `-DeclRefExpr <col:14> 'bool' lvalue ParmVar 0x55a0e17465d0 'a' 'bool'
      `-UnaryOperator <col:19, col:20> 'bool' prefix '!' cannot overflow
        `-ImplicitCastExpr <col:20> 'bool' <LValueToRValue>
          `-DeclRefExpr <col:20> 'bool' lvalue ParmVar 0x55a0e1746648 'b' 'bool'
LegalizeAdulthood marked 2 inline comments as done.May 2 2022, 9:55 AM
LegalizeAdulthood added inline comments.
clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp
598–599

I've noticed that some matchers peek through parens, that must be what's going on here that allows it to match without explicitly matching the parenExpr.

LegalizeAdulthood marked 2 inline comments as done.May 2 2022, 9:56 AM

I've done my own implementation, but its definitely over engineered, WDYT? D124806

I've done my own implementation, but its definitely over engineered, WDYT? D124806

Hey, that looks great at a glance. I need to prepare for Utah C++ Programmers presentation on Wednesday, so I won't be able to revisit these recent reviews until next weekend probably.

Discarding in favor of Nathan James's improved implementation.