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

[LegalizeAdulthood]

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

[LegalizeAdulthood]

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]

clang-tools-extra/docs/ReleaseNotes.rst

139

Please use alphabetical order for such entries.

[LegalizeAdulthood]

Sort changes by check name in docs

[LegalizeAdulthood]

In D124650#3481514, @LegalizeAdulthood wrote:

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.

[LegalizeAdulthood]

Surround replacements with parens

[njames93]

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]

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.

[LegalizeAdulthood]

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.

[LegalizeAdulthood]

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.

[LegalizeAdulthood]

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]

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]

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]

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.

[njames93]

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

[LegalizeAdulthood]

In D124650#3486859, @njames93 wrote:

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.

[LegalizeAdulthood]

Discarding in favor of Nathan James's improved implementation.

clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.h

void matchCaseIfReturnsBool(ast_matchers::MatchFinder *Finder, bool Value,
                               StringRef Id);
 
   void matchDefaultIfReturnsBool(ast_matchers::MatchFinder *Finder, bool Value,
                                  StringRef Id);
 
   void matchLabelIfReturnsBool(ast_matchers::MatchFinder *Finder, bool Value,
                                StringRef Id);
 
+  void matchDeMorganExpr(ast_matchers::MatchFinder *Finder);
+
   void
   replaceWithThenStatement(const ast_matchers::MatchFinder::MatchResult &Result,
                            const Expr *BoolLiteral);
 
   void
   replaceWithElseStatement(const ast_matchers::MatchFinder::MatchResult &Result,
                            const Expr *BoolLiteral);
 
   void
   replaceWithCondition(const ast_matchers::MatchFinder::MatchResult &Result,
                        const ConditionalOperator *Ternary, bool Negated);
 
   void replaceWithReturnCondition(
       const ast_matchers::MatchFinder::MatchResult &Result, const IfStmt *If,
       bool Negated);
 
-  void
-  replaceWithAssignment(const ast_matchers::MatchFinder::MatchResult &Result,
-                        const IfStmt *If, bool Negated);
-
   void replaceCompoundReturnWithCondition(
       const ast_matchers::MatchFinder::MatchResult &Result,
       const CompoundStmt *Compound, bool Negated);
 
   void replaceCompoundReturnWithCondition(
       const ast_matchers::MatchFinder::MatchResult &Result, bool Negated,
       const IfStmt *If);
 
   void replaceCaseCompoundReturnWithCondition(
       const ast_matchers::MatchFinder::MatchResult &Result, bool Negated);
 
   void replaceDefaultCompoundReturnWithCondition(
       const ast_matchers::MatchFinder::MatchResult &Result, bool Negated);
 
   void replaceLabelCompoundReturnWithCondition(
       const ast_matchers::MatchFinder::MatchResult &Result, bool Negated);
 
+  void
+  replaceWithAssignment(const ast_matchers::MatchFinder::MatchResult &Result,
+                        const IfStmt *If, bool Negated);
+
+  bool
+  simplifyDeMorganExpr(const ast_matchers::MatchFinder::MatchResult &Result,
+                       const Expr *OrLeft, bool NotLeft, StringRef Op,
+                       bool NotRight);
+
   void issueDiag(const ast_matchers::MatchFinder::MatchResult &Result,
                  SourceLocation Loc, StringRef Description,
                  SourceRange ReplacementRange, StringRef Replacement);
 
   const bool ChainedConditionalReturn;
   const bool ChainedConditionalAssignment;
+  const bool SimplifyDeMorgan;
 };
 
 } // namespace readability
 } // namespace tidy
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_READABILITY_SIMPLIFY_BOOLEAN_EXPR_H

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

 static constexpr char CaseCompoundNotBoolId[] = "case-compound-bool-not";
 static constexpr char DefaultId[] = "default";
 static constexpr char DefaultCompoundBoolId[] = "default-compound-bool";
 static constexpr char DefaultCompoundNotBoolId[] = "default-compound-bool-not";
 static constexpr char LabelId[] = "label";
 static constexpr char LabelCompoundBoolId[] = "label-compound-bool";
 static constexpr char LabelCompoundNotBoolId[] = "label-compound-bool-not";
 static constexpr char IfStmtId[] = "if";
+static constexpr char LeftId[] = "left";
+static constexpr char RightId[] = "right";
+static constexpr char DeMorganOrLeftId[] = "demorgan-or-left";
+static constexpr char DeMorganOrRightId[] = "demorgan-or-right";
+static constexpr char DeMorganOrBothId[] = "demorgan-or-both";
+static constexpr char DeMorganAndLeftId[] = "demorgan-and-left";
+static constexpr char DeMorganAndRightId[] = "demorgan-and-right";
+static constexpr char DeMorganAndBothId[] = "demorgan-and-both";
 
 static constexpr char SimplifyOperatorDiagnostic[] =
     "redundant boolean literal supplied to boolean operator";
 static constexpr char SimplifyConditionDiagnostic[] =
     "redundant boolean literal in if statement condition";
 static constexpr char SimplifyConditionalReturnDiagnostic[] =
     "redundant boolean literal in conditional return statement";
 
private:
   const MatchFinder::MatchResult &Result;
 };
 
 SimplifyBooleanExprCheck::SimplifyBooleanExprCheck(StringRef Name,
                                                    ClangTidyContext *Context)
     : ClangTidyCheck(Name, Context),
       ChainedConditionalReturn(Options.get("ChainedConditionalReturn", false)),
       ChainedConditionalAssignment(
-          Options.get("ChainedConditionalAssignment", false)) {}
+          Options.get("ChainedConditionalAssignment", false)),
+      SimplifyDeMorgan(Options.get("SimplifyDeMorgan", true)) {}
 
 static bool containsBoolLiteral(const Expr *E) {
   if (!E)
     return false;
   E = E->IgnoreParenImpCasts();
   if (isa<CXXBoolLiteralExpr>(E))
     return true;
   if (const auto *BinOp = dyn_cast<BinaryOperator>(E))
void SimplifyBooleanExprCheck::matchLabelIfReturnsBool(MatchFinder *Finder,
   internal::Matcher<Stmt> LabelStmt =
       labelStmt(hasSubstatement(ifReturnValue(Value))).bind(LabelId);
   internal::Matcher<Stmt> CompoundStmt =
       compoundStmt(hasSubstatementSequence(LabelStmt, returnNotValue(Value)))
           .bind(Id);
   Finder->addMatcher(CompoundStmt, this);
 }
 
+void SimplifyBooleanExprCheck::matchDeMorganExpr(MatchFinder *Finder) {
+  if (!SimplifyDeMorgan)
+    return;
+
+  auto Not = hasOperatorName("!");
+  auto Or = hasOperatorName("||");
+  auto And = hasOperatorName("&&");
+  auto LHSExpr = expr().bind(LeftId);
+  auto RHSExpr = expr().bind(RightId);
+  auto NotOp = unaryOperator(Not);
+  auto LHS = hasLHS(LHSExpr);
+  auto RHS = hasRHS(RHSExpr);
+  auto NotLHS = hasLHS(unaryOperator(Not, hasUnaryOperand(LHSExpr)));
+  auto NotRHS = hasRHS(unaryOperator(Not, hasUnaryOperand(RHSExpr)));
+  auto UnlessNotRHS = unless(hasRHS(NotOp));
+  auto UnlessNotLHS = unless(hasLHS(NotOp));
+  // match !(!a || b)
+  Finder->addMatcher(unaryOperator(Not, hasUnaryOperand(binaryOperator(
+                                            Or, UnlessNotRHS, NotLHS, RHS)))
+                         .bind(DeMorganOrLeftId),
+                     this);
+  // match !(a || !b)
+  Finder->addMatcher(unaryOperator(Not, hasUnaryOperand(binaryOperator(
+                                            Or, UnlessNotLHS, LHS, NotRHS)))
+                         .bind(DeMorganOrRightId),
+                     this);
+  // match !(!a || !b)
+  Finder->addMatcher(
+      unaryOperator(Not, hasUnaryOperand(binaryOperator(Or, NotLHS, NotRHS)))
+          .bind(DeMorganOrBothId),
+      this);
+
+  // match !(!a && b)
+  Finder->addMatcher(unaryOperator(Not, hasUnaryOperand(binaryOperator(
+                                            And, UnlessNotRHS, NotLHS, RHS)))
+                         .bind(DeMorganAndLeftId),
+                     this);
+  // match !(a && !b)
+  Finder->addMatcher(unaryOperator(Not, hasUnaryOperand(binaryOperator(
+                                            And, UnlessNotLHS, LHS, NotRHS)))
+                         .bind(DeMorganAndRightId),
+                     this);
+  // match !(!a && !b)
+  Finder->addMatcher(
+      unaryOperator(Not, hasUnaryOperand(binaryOperator(And, NotLHS, NotRHS)))
+          .bind(DeMorganAndBothId),
+      this);
+}
+
 void SimplifyBooleanExprCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
   Options.store(Opts, "ChainedConditionalReturn", ChainedConditionalReturn);
   Options.store(Opts, "ChainedConditionalAssignment",
                 ChainedConditionalAssignment);
+  Options.store(Opts, "SimplifyDeMorgan", SimplifyDeMorgan);
 }
 
 void SimplifyBooleanExprCheck::registerMatchers(MatchFinder *Finder) {
   Finder->addMatcher(translationUnitDecl().bind("top"), this);
 
   matchBoolCondition(Finder, true, ConditionThenStmtId);
   matchBoolCondition(Finder, false, ConditionElseStmtId);
 
void SimplifyBooleanExprCheck::registerMatchers(MatchFinder *Finder) {
   matchCaseIfReturnsBool(Finder, true, CaseCompoundBoolId);
   matchCaseIfReturnsBool(Finder, false, CaseCompoundNotBoolId);
 
   matchDefaultIfReturnsBool(Finder, true, DefaultCompoundBoolId);
   matchDefaultIfReturnsBool(Finder, false, DefaultCompoundNotBoolId);
 
   matchLabelIfReturnsBool(Finder, true, LabelCompoundBoolId);
   matchLabelIfReturnsBool(Finder, false, LabelCompoundNotBoolId);
+
+  matchDeMorganExpr(Finder);
 }
 
 void SimplifyBooleanExprCheck::check(const MatchFinder::MatchResult &Result) {
   if (Result.Nodes.getNodeAs<TranslationUnitDecl>("top"))
     Visitor(this, Result).TraverseAST(*Result.Context);
   else if (const Expr *TrueConditionRemoved =
                getBoolLiteral(Result, ConditionThenStmtId))
     replaceWithThenStatement(Result, TrueConditionRemoved);
void SimplifyBooleanExprCheck::check(const MatchFinder::MatchResult &Result) {
   else if (Result.Nodes.getNodeAs<CompoundStmt>(DefaultCompoundNotBoolId))
     replaceDefaultCompoundReturnWithCondition(Result, true);
   else if (Result.Nodes.getNodeAs<CompoundStmt>(LabelCompoundBoolId))
     replaceLabelCompoundReturnWithCondition(Result, false);
   else if (Result.Nodes.getNodeAs<CompoundStmt>(LabelCompoundNotBoolId))
     replaceLabelCompoundReturnWithCondition(Result, true);
   else if (const auto TU = Result.Nodes.getNodeAs<Decl>("top"))
     Visitor(this, Result).TraverseDecl(const_cast<Decl *>(TU));
+  else if (const auto *OrLeft = Result.Nodes.getNodeAs<Expr>(DeMorganOrLeftId))
+    simplifyDeMorganExpr(Result, OrLeft, false, "&&", true);
+  else if (const auto *OrRight =
+               Result.Nodes.getNodeAs<Expr>(DeMorganOrRightId))
+    simplifyDeMorganExpr(Result, OrRight, true, "&&", false);
+  else if (const auto *OrBoth = Result.Nodes.getNodeAs<Expr>(DeMorganOrBothId))
+    simplifyDeMorganExpr(Result, OrBoth, false, "&&", false);
+  else if (const auto *AndLeft =
+               Result.Nodes.getNodeAs<Expr>(DeMorganAndLeftId))
+    simplifyDeMorganExpr(Result, AndLeft, false, "||", true);
+  else if (const auto *AndRight =
+               Result.Nodes.getNodeAs<Expr>(DeMorganAndRightId))
+    simplifyDeMorganExpr(Result, AndRight, true, "||", false);
+  else if (const auto *AndBoth =
+               Result.Nodes.getNodeAs<Expr>(DeMorganAndBothId))
+    simplifyDeMorganExpr(Result, AndBoth, false, "||", false);
 }
 
 void SimplifyBooleanExprCheck::issueDiag(const MatchFinder::MatchResult &Result,
                                          SourceLocation Loc,
                                          StringRef Description,
                                          SourceRange ReplacementRange,
                                          StringRef Replacement) {
   CharSourceRange CharRange =
std::string Replacement =
       (VariableName + " = " + Condition + Terminator).str();
   SourceLocation Location =
       Result.Nodes.getNodeAs<CXXBoolLiteralExpr>(IfAssignLocId)->getBeginLoc();
   issueDiag(Result, Location,
             "redundant boolean literal in conditional assignment", Range,
             Replacement);
 }
 
+bool SimplifyBooleanExprCheck::simplifyDeMorganExpr(
+    const MatchFinder::MatchResult &Result, const Expr *OrLeft, bool NotLeft,
+    StringRef Op, bool NotRight) {
+  if (!SimplifyDeMorgan)
+    return true;
+
+  const Expr *Left = Result.Nodes.getNodeAs<Expr>(LeftId);
+  const Expr *Right = Result.Nodes.getNodeAs<Expr>(RightId);
+  std::string Replacement =
+      ((NotLeft ? "!" : "") + getText(Result, *Left) + " " + Op + " " +
+       (NotRight ? "!" : "") + getText(Result, *Right))
+          .str();
+  SourceLocation Loc = OrLeft->getBeginLoc();
+  SourceRange Range = OrLeft->getSourceRange();
+  issueDiag(Result, Loc,
+            "boolean expression can be simplified by DeMorgan's theorem", Range,
+            Replacement);
+  return false;
+}
+
 } // namespace readability
 } // namespace tidy
 } // namespace clang

clang-tools-extra/docs/ReleaseNotes.rst

 
 - New alias :doc:`cppcoreguidelines-macro-to-enum
   <clang-tidy/checks/cppcoreguidelines-macro-to-enum>` to :doc:`modernize-macro-to-enum
   <clang-tidy/checks/modernize-macro-to-enum>` was added.
 
 Changes in existing checks
 ^^^^^^^^^^^^^^^^^^^^^^^^^^
 
+- Expanded :doc:`readability-simplify-boolean-expr
+  <clang-tidy/checks/readability-simplify-boolean-expr>` to simplify expressions
+  using DeMorgan's Theorem.
+
 - Fixed a crash in :doc:`bugprone-sizeof-expression
   <clang-tidy/checks/bugprone-sizeof-expression>` when `sizeof(...)` is
   compared against a `__int128_t`.
 
 - Improved :doc:`cppcoreguidelines-prefer-member-initializer
   <clang-tidy/checks/cppcoreguidelines-prefer-member-initializer>` check.
 
   Fixed an issue when there was already an initializer in the constructor and

clang-tools-extra/docs/clang-tidy/checks/readability-simplify-boolean-expr.rst

 .. title:: clang-tidy - readability-simplify-boolean-expr
 
 readability-simplify-boolean-expr
 =================================
 
 Looks for boolean expressions involving boolean constants and simplifies
-them to use the appropriate boolean expression directly.
+them to use the appropriate boolean expression directly.  Simplifies
+boolean expressions by application of DeMorgan's Theorem.
 
 Examples:
 
 ===========================================  ================
 Initial expression                           Result
 -------------------------------------------  ----------------
 ``if (b == true)``                             ``if (b)``
 ``if (b == false)``                            ``if (!b)``
 ``if (b && true)``                             ``if (b)``
 ``if (b && false)``                            ``if (false)``
 ``if (b || true)``                             ``if (true)``
 ``if (b || false)``                            ``if (b)``
 ``e ? true : false``                           ``e``
 ``e ? false : true``                           ``!e``
 ``if (true) t(); else f();``                   ``t();``
 ``if (false) t(); else f();``                  ``f();``
 ``if (e) return true; else return false;``     ``return e;``
 ``if (e) return false; else return true;``     ``return !e;``
 ``if (e) b = true; else b = false;``           ``b = e;``
 ``if (e) b = false; else b = true;``           ``b = !e;``
 ``if (e) return true; return false;``          ``return e;``
 ``if (e) return false; return true;``          ``return !e;``
+``!(!a || b)``                                 ``a && !b``
+``!(a || !b)``                                 ``!a && b``
+``!(!a || !b)``                                ``a && b``
+``!(!a && b)``                                 ``a || !b``
+``!(a && !b)``                                 ``!a || b``
+``!(!a && !b)``                                ``a || b``
 ===========================================  ================
 
 The resulting expression ``e`` is modified as follows:
   1. Unnecessary parentheses around the expression are removed.
   2. Negated applications of ``!`` are eliminated.
   3. Negated applications of comparison operators are changed to use the
      opposite condition.
   4. Implicit conversions of pointers, including pointers to members, to
.. option:: ChainedConditionalReturn
 
    If `true`, conditional boolean return statements at the end of an
    ``if/else if`` chain will be transformed. Default is `false`.
 
 .. option:: ChainedConditionalAssignment
 
    If `true`, conditional boolean assignments at the end of an ``if/else
    if`` chain will be transformed. Default is `false`.
+
+.. option:: SimplifyDeMorgan
+
+   If `true`, DeMorgan's Theorem will be applied to simplify negated
+   conjunctions and disjunctions.  Default is `true`.

clang-tools-extra/test/clang-tidy/checkers/readability-simplify-bool-expr-demorgan.cpp

+// RUN: %check_clang_tidy %s readability-simplify-boolean-expr %t -- -config="{CheckOptions: [{key: "readability-simplify-boolean-expr.SimplifyDeMorgan", value: true}]}" --
+
+bool a1 = false;
+bool a2 = false;
+
+bool aa = !(!a1 || a2);
+bool ab = !(a1 || !a2);
+bool ac = !(!a1 || !a2);
+// CHECK-MESSAGES: :[[@LINE-3]]:11: warning: boolean expression can be simplified by DeMorgan's theorem [readability-simplify-boolean-expr]
+// CHECK-MESSAGES: :[[@LINE-3]]:11: warning: boolean expression can be simplified by DeMorgan's theorem [readability-simplify-boolean-expr]
+// CHECK-MESSAGES: :[[@LINE-3]]:11: warning: boolean expression can be simplified by DeMorgan's theorem [readability-simplify-boolean-expr]
+// CHECK-FIXES: {{^bool aa = a1 && !a2;$}}
+// CHECK-FIXES-NEXT: {{^bool ab = !a1 && a2;$}}
+// CHECK-FIXES-NEXT: {{^bool ac = a1 && a2;$}}
+
+bool ba = !(!a1 && a2);
+bool bb = !(a1 && !a2);
+bool bc = !(!a1 && !a2);
+// CHECK-MESSAGES: :[[@LINE-3]]:11: warning: boolean expression can be simplified by DeMorgan's theorem [readability-simplify-boolean-expr]
+// CHECK-MESSAGES: :[[@LINE-3]]:11: warning: boolean expression can be simplified by DeMorgan's theorem [readability-simplify-boolean-expr]
+// CHECK-MESSAGES: :[[@LINE-3]]:11: warning: boolean expression can be simplified by DeMorgan's theorem [readability-simplify-boolean-expr]
+// CHECK-FIXES: {{^bool ba = a1 }}||{{ !a2;$}}
+// CHECK-FIXES-NEXT: {{^bool bb = !a1 }}||{{ a2;$}}
+// CHECK-FIXES-NEXT: {{^bool bc = a1 }}||{{ a2;$}}