[clang-tidy] add support for Demorgan conversions to readability-simplify-bool-expr

[njames93]

Summary

Adds support for recognising and converting boolean expressions that can be simplified using De Morgans Law.

This is a different implementation to D124650.

Fixes https://github.com/llvm/llvm-project/issues/55092

[njames93]

Small update

[njames93]

Add tracking info to prevented nested cases from emitting conflicting fixes, disabled for use cases like clangd.
Prevent emitting fixes in macro expansions.

[njames93]

Enhanced support for parens, both adding them in when needed as well as removing some un-needed parens.

[njames93]

Reimplement matchers as an ASTVisitor instead.
This massively simplifies the tracking of nested cases.

[njames93]

Added release notes.
Fix build issues with previous push.

[njames93]

Tweak fix to not remove parens if it will result in a LogicalOpParentheses warning.

[njames93]

Rebased.

[njames93]

Extend fix-its to also support removing parens where possible.

[LegalizeAdulthood]

LGTM! Thanks for taking my idea and implementing it much better than what I had :).

[njames93]

In D124806#3523109, @LegalizeAdulthood wrote:

LGTM! Thanks for taking my idea and implementing it much better than what I had :).

Cheers.
Can I ask why you feel that this should be behind an option?
Also do you think there is merit in handling the case !(A && B) -> !A || !B obviously that could be behind an option.

[njames93]

Remove unnecessary parens in documentation as check will remove the parens when possible.

[LegalizeAdulthood]

In D124806#3523228, @njames93 wrote:

In D124806#3523109, @LegalizeAdulthood wrote:

LGTM! Thanks for taking my idea and implementing it much better than what I had :).

Cheers.
Can I ask why you feel that this should be behind an option?

When I've brought it up in manual code reviews before, there were some objections.
That's why I thought it was worth adding an option to disable it. Many people aren't
even familiar with DeMorgan's Theorem/Law and might be afraid that the simplification
changes semantics, although the underlying github issue shows that this is not the case.

Also do you think there is merit in handling the case !(A && B) -> !A || !B obviously that could be behind an option.

The reason I proposed the simplification !(!A && B) -> A || !B is because the former employs
"double negatives" and provides a stumbling block for readability. All readability "checks"
are somewhat influenced by opinion and style to a certain extent, but I think the avoid
"double negative" idea is widely accepted.

In the case of !(A && B) -> !A || !B, no double negative is involved and one could argue
that it went from one negative to two, which is why I didn't include that in my original
proposal. The "goodness" of it just doesn't seem universal and personally if the check
grew to enable that case, I'd want an option to disable that behavior :).

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

 //===--- SimplifyBooleanExpr.h clang-tidy -----------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_READABILITY_SIMPLIFY_BOOLEAN_EXPR_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_READABILITY_SIMPLIFY_BOOLEAN_EXPR_H
 
 #include "../ClangTidyCheck.h"
+#include "llvm/ADT/DenseSet.h"
 
 namespace clang {
 namespace tidy {
 namespace readability {
 
 /// Looks for boolean expressions involving boolean constants and simplifies
 /// them to use the appropriate boolean expression directly.
 ///
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 replaceDeMorgan(const UnaryOperator *Outer, const BinaryOperator *Inner);
+
   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;
+  llvm::DenseSet<const UnaryOperator *> DemorganOps;
 };
 
 } // 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

 //===-- SimplifyBooleanExprCheck.cpp - clang-tidy -------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "SimplifyBooleanExprCheck.h"
 #include "SimplifyBooleanExprMatchers.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Lex/Lexer.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SmallVector.h"
 
 #include <string>
 #include <utility>
 
 using namespace clang::ast_matchers;
 
 namespace clang {
 namespace tidy {

 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 DeMorganID[] = "demorgan";
+static constexpr char DemorganInnerID[] = "demorganInner";
 
 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::storeOptions(ClangTidyOptions::OptionMap &Opts) {
   Options.store(Opts, "ChainedConditionalReturn", ChainedConditionalReturn);
   Options.store(Opts, "ChainedConditionalAssignment",
                 ChainedConditionalAssignment);
 }
 
+namespace {
+AST_MATCHER(BinaryOperator, isNegateableComparisonOperator) {
+  switch (Node.getOpcode()) {
+  case BO_LT:
+  case BO_GT:
+  case BO_LE:
+  case BO_GE:
+  case BO_EQ:
+  case BO_NE:
+    return true;
+  default:
+    return false;
+  }
+}
+} // namespace
+
 void SimplifyBooleanExprCheck::registerMatchers(MatchFinder *Finder) {
   Finder->addMatcher(translationUnitDecl().bind("top"), this);
 
   matchBoolCondition(Finder, true, ConditionThenStmtId);
   matchBoolCondition(Finder, false, ConditionElseStmtId);
 
   matchTernaryResult(Finder, true, TernaryId);
   matchTernaryResult(Finder, false, TernaryNegatedId);
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);
+
+  if (SimplifyDeMorgan) {
+    Finder->addMatcher(
+        unaryOperator(
+            hasOperatorName("!"),
+            hasUnaryOperand(ignoringParens(
+                binaryOperator(
+                    hasAnyOperatorName("&&", "||"), hasType(booleanType()),
+                    hasEitherOperand(anyOf(
+                        unaryOperator(hasOperatorName("!")),
+                        binaryOperator(isNegateableComparisonOperator()))))
+                    .bind(DemorganInnerID))))
+            .bind(DeMorganID),
+        this);
+  }
 }
 
 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 *DMT = Result.Nodes.getNodeAs<UnaryOperator>(DeMorganID))
+    replaceDeMorgan(DMT,
+                    Result.Nodes.getNodeAs<BinaryOperator>(DemorganInnerID));
 }
 
 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);
 }
 
+/// Swaps a \c BinaryOperator opcode from `&&` to `||` or vice-versa.
+static bool flipDemorganOperator(llvm::SmallVectorImpl<FixItHint> &Output,
+                                 const BinaryOperator *BO) {
+  assert(BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr);
+  if (BO->getOperatorLoc().isMacroID())
+    return true;
+  Output.push_back(FixItHint::CreateReplacement(
+      BO->getOperatorLoc(), BO->getOpcode() == BO_LAnd ? "||" : "&&"));
+  return false;
+}
+
+static bool
+flipDemorganSide(llvm::SmallVectorImpl<FixItHint> &Output, const Expr *E,
+                 llvm::SmallVectorImpl<const UnaryOperator *> &TUTracker);
+
+static bool flipDemorganBinaryOperator(
+    llvm::SmallVectorImpl<FixItHint> &Output, const BinaryOperator *BinOp,
+    llvm::SmallVectorImpl<const UnaryOperator *> &TUTracker,
+    const ParenExpr *Parens = nullptr) {
+  switch (BinOp->getOpcode()) {
+  case BO_LAnd:
+  case BO_LOr:
+    // if we have 'a && b' or 'a || b', use demorgan to flip it to '!a || !b'
+    // or '!a && !b'.
+    if (flipDemorganOperator(Output, BinOp))
+      return true;
+    return flipDemorganSide(Output, BinOp->getLHS(), TUTracker) ||
+           flipDemorganSide(Output, BinOp->getRHS(), TUTracker);
+  case BO_LT:
+  case BO_GT:
+  case BO_LE:
+  case BO_GE:
+  case BO_EQ:
+  case BO_NE:
+    // For comparison operators, just negate the comparison.
+    if (BinOp->getOperatorLoc().isMacroID())
+      return true;
+    Output.push_back(FixItHint::CreateReplacement(
+        BinOp->getOperatorLoc(),
+        BinaryOperator::getOpcodeStr(
+            BinaryOperator::negateComparisonOp(BinOp->getOpcode()))));
+    return false;
+  default:
+    // for any other binary operator, just use logical not and wrap in
+    // parens.
+    if (Parens) {
+      if (Parens->getBeginLoc().isMacroID())
+        return true;
+      Output.push_back(FixItHint::CreateInsertion(Parens->getBeginLoc(), "!"));
+    } else {
+      if (BinOp->getBeginLoc().isMacroID() || BinOp->getEndLoc().isMacroID())
+        return true;
+      Output.append({FixItHint::CreateInsertion(BinOp->getBeginLoc(), "!("),
+                     FixItHint::CreateInsertion(
+                         BinOp->getEndLoc().getLocWithOffset(1), ")")});
+    }
+    break;
+  }
+  return false;
+}
+
+static bool
+flipDemorganSide(llvm::SmallVectorImpl<FixItHint> &Output, const Expr *E,
+                 SmallVectorImpl<const UnaryOperator *> &TUTracker) {
+  if (isa<UnaryOperator>(E) && cast<UnaryOperator>(E)->getOpcode() == UO_LNot) {
+    TUTracker.push_back(cast<UnaryOperator>(E));
+    // if we have a not operator, '!a', just remove the '!'.
+    if (cast<UnaryOperator>(E)->getOperatorLoc().isMacroID())
+      return true;
+    Output.push_back(
+        FixItHint::CreateRemoval(cast<UnaryOperator>(E)->getOperatorLoc()));
+    return false;
+  }
+  if (const auto *BinOp = dyn_cast<BinaryOperator>(E)) {
+    return flipDemorganBinaryOperator(Output, BinOp, TUTracker);
+  }
+  if (const auto *Paren = dyn_cast<ParenExpr>(E)) {
+    if (const auto *BinOp = dyn_cast<BinaryOperator>(Paren->getSubExpr())) {
+      return flipDemorganBinaryOperator(Output, BinOp, TUTracker, Paren);
+    }
+  }
+  // Fallback case just insert a logical not operator.
+  if (E->getBeginLoc().isMacroID())
+    return true;
+  Output.push_back(FixItHint::CreateInsertion(E->getBeginLoc(), "!"));
+  return false;
+}
+
+void SimplifyBooleanExprCheck::replaceDeMorgan(const UnaryOperator *Outer,
+                                               const BinaryOperator *Inner) {
+  assert(Outer);
+  assert(Inner);
+  assert(Inner->getOpcode() == BO_LAnd || Inner->getOpcode() == BO_LOr);
+
+  auto Diag =
+      diag(Outer->getBeginLoc(),
+           "boolean expression can be simplified by DeMorgan's theorem");
+  Diag << Outer->getSourceRange();
+  // If we have already fixed this with a previous fix, don't attempt any fixes
+  if (!areDiagsSelfContained() && !DemorganOps.insert(Outer).second)
+    return;
+  if (Outer->getOperatorLoc().isMacroID())
+    return;
+  SmallVector<FixItHint, 8> Fixes;
+  Fixes.push_back(FixItHint::CreateRemoval(Outer->getOperatorLoc()));
+  if (flipDemorganOperator(Fixes, Inner))
+    return;
+  llvm::SmallVector<const UnaryOperator *> Tracker;
+  if (flipDemorganSide(Fixes, Inner->getLHS(), Tracker))
+    return;
+  if (flipDemorganSide(Fixes, Inner->getRHS(), Tracker))
+    return;
+  Diag << Fixes;
+  if (!areDiagsSelfContained()) {
+    DemorganOps.insert(Tracker.begin(), Tracker.end());
+  }
+}
 } // namespace readability
 } // namespace tidy
 } // namespace clang

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
+
+void foo(bool A1, bool A2, bool A3) {
+  bool X;
+  X = !(!A1 || A2);
+  X = !(A1 || !A2);
+  X = !(!A1 || !A2);
+  // CHECK-MESSAGES: :[[@LINE-3]]:7: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-MESSAGES: :[[@LINE-3]]:7: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-MESSAGES: :[[@LINE-3]]:7: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-FIXES: X = (A1 && !A2);
+  // CHECK-FIXES-NEXT: X = (!A1 && A2);
+  // CHECK-FIXES-NEXT: X = (A1 && A2);
+
+  X = !(!A1 && A2);
+  X = !(A1 && !A2);
+  X = !(!A1 && !A2);
+  // CHECK-MESSAGES: :[[@LINE-3]]:7: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-MESSAGES: :[[@LINE-3]]:7: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-MESSAGES: :[[@LINE-3]]:7: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-FIXES: X = (A1 || !A2);
+  // CHECK-FIXES-NEXT: X = (!A1 || A2);
+  // CHECK-FIXES-NEXT: X = (A1 || A2);
+
+  X = !(!A1 && !A2 && !A3);
+  X = !(!A1 && (!A2 && !A3));
+  X = !(!A1 && (A2 && A3));
+  // CHECK-MESSAGES: :[[@LINE-3]]:7: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-MESSAGES: :[[@LINE-3]]:7: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-MESSAGES: :[[@LINE-3]]:7: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-FIXES: X = (A1 || A2 || A3);
+  // CHECK-FIXES-NEXT: X = (A1 || (A2 || A3));
+  // CHECK-FIXES-NEXT: X = (A1 || (!A2 || !A3));
+
+  X = !(A1 && A2 == A3);
+  X = !(!A1 && A2 > A3);
+  // CHECK-MESSAGES: :[[@LINE-2]]:7: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-MESSAGES: :[[@LINE-2]]:7: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-FIXES: X = (!A1 || A2 != A3);
+  // CHECK-FIXES-NEXT: X = (A1 || A2 <= A3);
+
+  // Ensure the check doesn't try to combine fixes for the inner and outer demorgan simplification.
+  X = !(!A1 && !(!A2 && !A3));
+  // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-MESSAGES: :[[@LINE-2]]:16: warning: boolean expression can be simplified by DeMorgan's theorem
+  // CHECK-FIXES: X = (A1 || (!A2 && !A3));
+}