diff --git a/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.h b/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.h --- a/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.h +++ b/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.h @@ -10,6 +10,7 @@ #define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_READABILITY_SIMPLIFY_BOOLEAN_EXPR_H #include "../ClangTidyCheck.h" +#include "llvm/ADT/DenseSet.h" namespace clang { namespace tidy { @@ -98,12 +99,16 @@ 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 DemorganOps; }; } // namespace readability diff --git a/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp b/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp --- a/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp +++ b/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp @@ -10,6 +10,8 @@ #include "SimplifyBooleanExprMatchers.h" #include "clang/AST/RecursiveASTVisitor.h" #include "clang/Lex/Lexer.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SmallVector.h" #include #include @@ -61,6 +63,8 @@ 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"; @@ -371,7 +375,8 @@ : 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) @@ -576,6 +581,22 @@ 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); @@ -602,6 +623,21 @@ 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) { @@ -650,6 +686,9 @@ replaceLabelCompoundReturnWithCondition(Result, true); else if (const auto TU = Result.Nodes.getNodeAs("top")) Visitor(this, Result).TraverseDecl(const_cast(TU)); + else if (const auto *DMT = Result.Nodes.getNodeAs(DeMorganID)) + replaceDeMorgan(DMT, + Result.Nodes.getNodeAs(DemorganInnerID)); } void SimplifyBooleanExprCheck::issueDiag(const MatchFinder::MatchResult &Result, @@ -787,6 +826,123 @@ Replacement); } +/// Swaps a \c BinaryOperator opcode from `&&` to `||` or vice-versa. +static bool flipDemorganOperator(llvm::SmallVectorImpl &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 &Output, const Expr *E, + llvm::SmallVectorImpl &TUTracker); + +static bool flipDemorganBinaryOperator( + llvm::SmallVectorImpl &Output, const BinaryOperator *BinOp, + llvm::SmallVectorImpl &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 &Output, const Expr *E, + SmallVectorImpl &TUTracker) { + if (isa(E) && cast(E)->getOpcode() == UO_LNot) { + TUTracker.push_back(cast(E)); + // if we have a not operator, '!a', just remove the '!'. + if (cast(E)->getOperatorLoc().isMacroID()) + return true; + Output.push_back( + FixItHint::CreateRemoval(cast(E)->getOperatorLoc())); + return false; + } + if (const auto *BinOp = dyn_cast(E)) { + return flipDemorganBinaryOperator(Output, BinOp, TUTracker); + } + if (const auto *Paren = dyn_cast(E)) { + if (const auto *BinOp = dyn_cast(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 Fixes; + Fixes.push_back(FixItHint::CreateRemoval(Outer->getOperatorLoc())); + if (flipDemorganOperator(Fixes, Inner)) + return; + llvm::SmallVector 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 diff --git a/clang-tools-extra/docs/clang-tidy/checks/readability-simplify-boolean-expr.rst b/clang-tools-extra/docs/clang-tidy/checks/readability-simplify-boolean-expr.rst --- a/clang-tools-extra/docs/clang-tidy/checks/readability-simplify-boolean-expr.rst +++ b/clang-tools-extra/docs/clang-tidy/checks/readability-simplify-boolean-expr.rst @@ -4,7 +4,8 @@ ================================= 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: @@ -27,6 +28,12 @@ ``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: @@ -84,3 +91,8 @@ 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`. diff --git a/clang-tools-extra/test/clang-tidy/checkers/readability-simplify-bool-expr-demorgan.cpp b/clang-tools-extra/test/clang-tidy/checkers/readability-simplify-bool-expr-demorgan.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/test/clang-tidy/checkers/readability-simplify-bool-expr-demorgan.cpp @@ -0,0 +1,47 @@ +// 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)); +}