From af77b1d99016fde66edd9e72d907c03fe4511215 Mon Sep 17 00:00:00 2001 From: Nathan James Date: Sun, 22 May 2022 09:28:39 +0100 Subject: [PATCH] [clang-tidy] add support for Demorgan conversions to readability-simplify-bool-expr 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 Reviewed By: LegalizeAdulthood Differential Revision: https://reviews.llvm.org/D124806 --- .../readability/SimplifyBooleanExprCheck.cpp | 262 ++++++++++++++++++++- .../readability/SimplifyBooleanExprCheck.h | 5 + clang-tools-extra/docs/ReleaseNotes.rst | 4 + .../checks/readability-simplify-boolean-expr.rst | 14 +- .../readability-simplify-bool-expr-demorgan.cpp | 87 +++++++ 5 files changed, 370 insertions(+), 2 deletions(-) create mode 100644 clang-tools-extra/test/clang-tidy/checkers/readability-simplify-bool-expr-demorgan.cpp diff --git a/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp b/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp index 323cf1f..3502375 100644 --- a/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp +++ b/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.cpp @@ -9,6 +9,7 @@ #include "SimplifyBooleanExprCheck.h" #include "clang/AST/RecursiveASTVisitor.h" #include "clang/Lex/Lexer.h" +#include "llvm/Support/SaveAndRestore.h" #include #include @@ -257,6 +258,8 @@ static bool containsDiscardedTokens(const ASTContext &Context, } class SimplifyBooleanExprCheck::Visitor : public RecursiveASTVisitor { + using Base = RecursiveASTVisitor; + public: Visitor(SimplifyBooleanExprCheck *Check, ASTContext &Context) : Check(Check), Context(Context) {} @@ -503,7 +506,73 @@ public: return true; } + static bool isUnaryLNot(const Expr *E) { + return isa(E) && + cast(E)->getOpcode() == UO_LNot; + } + + template + static bool checkEitherSide(const BinaryOperator *BO, Functor Func) { + return Func(BO->getLHS()) || Func(BO->getRHS()); + } + + static bool nestedDemorgan(const Expr *E, unsigned NestingLevel) { + const auto *BO = dyn_cast(E->IgnoreUnlessSpelledInSource()); + if (!BO) + return false; + if (!BO->getType()->isBooleanType()) + return false; + switch (BO->getOpcode()) { + case BO_LT: + case BO_GT: + case BO_LE: + case BO_GE: + case BO_EQ: + case BO_NE: + return true; + case BO_LAnd: + case BO_LOr: + if (checkEitherSide(BO, isUnaryLNot)) + return true; + if (NestingLevel) { + if (checkEitherSide(BO, [NestingLevel](const Expr *E) { + return nestedDemorgan(E, NestingLevel - 1); + })) + return true; + } + return false; + default: + return false; + } + } + + bool TraverseUnaryOperator(UnaryOperator *Op) { + if (!Check->SimplifyDeMorgan || Op->getOpcode() != UO_LNot) + return Base::TraverseUnaryOperator(Op); + Expr *SubImp = Op->getSubExpr()->IgnoreImplicit(); + auto *Parens = dyn_cast(SubImp); + auto *BinaryOp = + Parens + ? dyn_cast(Parens->getSubExpr()->IgnoreImplicit()) + : dyn_cast(SubImp); + if (!BinaryOp || !BinaryOp->isLogicalOp() || + !BinaryOp->getType()->isBooleanType()) + return Base::TraverseUnaryOperator(Op); + if (checkEitherSide(BinaryOp, isUnaryLNot) || + checkEitherSide(BinaryOp, + [](const Expr *E) { return nestedDemorgan(E, 1); })) { + if (Check->reportDeMorgan(Context, Op, BinaryOp, !IsProcessing, parent(), + Parens) && + !Check->areDiagsSelfContained()) { + llvm::SaveAndRestore RAII(IsProcessing, true); + return Base::TraverseUnaryOperator(Op); + } + } + return Base::TraverseUnaryOperator(Op); + } + private: + bool IsProcessing = false; SimplifyBooleanExprCheck *Check; SmallVector StmtStack; ASTContext &Context; @@ -514,7 +583,8 @@ SimplifyBooleanExprCheck::SimplifyBooleanExprCheck(StringRef Name, : 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) @@ -685,6 +755,196 @@ void SimplifyBooleanExprCheck::replaceWithAssignment(const ASTContext &Context, Range, Replacement); } +/// Swaps a \c BinaryOperator opcode from `&&` to `||` or vice-versa. +static bool flipDemorganOperator(llvm::SmallVectorImpl &Output, + const BinaryOperator *BO) { + assert(BO->isLogicalOp()); + if (BO->getOperatorLoc().isMacroID()) + return true; + Output.push_back(FixItHint::CreateReplacement( + BO->getOperatorLoc(), BO->getOpcode() == BO_LAnd ? "||" : "&&")); + return false; +} + +static BinaryOperatorKind getDemorganFlippedOperator(BinaryOperatorKind BO) { + assert(BinaryOperator::isLogicalOp(BO)); + return BO == BO_LAnd ? BO_LOr : BO_LAnd; +} + +static bool flipDemorganSide(SmallVectorImpl &Fixes, + const ASTContext &Ctx, const Expr *E, + Optional OuterBO); + +/// Inverts \p BinOp, Removing \p Parens if they exist and are safe to remove. +/// returns \c true if there is any issue building the Fixes, \c false +/// otherwise. +static bool flipDemorganBinaryOperator(SmallVectorImpl &Fixes, + const ASTContext &Ctx, + const BinaryOperator *BinOp, + Optional OuterBO, + 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(Fixes, BinOp)) + return true; + auto NewOp = getDemorganFlippedOperator(BinOp->getOpcode()); + if (OuterBO) { + // The inner parens are technically needed in a fix for + // `!(!A1 && !(A2 || A3)) -> (A1 || (A2 && A3))`, + // however this would trip the LogicalOpParentheses warning. + // FIXME: Make this user configurable or detect if that warning is + // enabled. + constexpr bool LogicalOpParentheses = true; + if (((*OuterBO == NewOp) || (!LogicalOpParentheses && + (*OuterBO == BO_LOr && NewOp == BO_LAnd))) && + Parens) { + if (!Parens->getLParen().isMacroID() && + !Parens->getRParen().isMacroID()) { + Fixes.push_back(FixItHint::CreateRemoval(Parens->getLParen())); + Fixes.push_back(FixItHint::CreateRemoval(Parens->getRParen())); + } + } + if (*OuterBO == BO_LAnd && NewOp == BO_LOr && !Parens) { + Fixes.push_back(FixItHint::CreateInsertion(BinOp->getBeginLoc(), "(")); + Fixes.push_back(FixItHint::CreateInsertion( + Lexer::getLocForEndOfToken(BinOp->getEndLoc(), 0, + Ctx.getSourceManager(), + Ctx.getLangOpts()), + ")")); + } + } + if (flipDemorganSide(Fixes, Ctx, BinOp->getLHS(), NewOp) || + flipDemorganSide(Fixes, Ctx, BinOp->getRHS(), NewOp)) + return true; + return false; + }; + 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; + Fixes.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; + Fixes.push_back(FixItHint::CreateInsertion(Parens->getBeginLoc(), "!")); + } else { + if (BinOp->getBeginLoc().isMacroID() || BinOp->getEndLoc().isMacroID()) + return true; + Fixes.append({FixItHint::CreateInsertion(BinOp->getBeginLoc(), "!("), + FixItHint::CreateInsertion( + Lexer::getLocForEndOfToken(BinOp->getEndLoc(), 0, + Ctx.getSourceManager(), + Ctx.getLangOpts()), + ")")}); + } + break; + } + return false; +} + +static bool flipDemorganSide(SmallVectorImpl &Fixes, + const ASTContext &Ctx, const Expr *E, + Optional OuterBO) { + if (isa(E) && cast(E)->getOpcode() == UO_LNot) { + // if we have a not operator, '!a', just remove the '!'. + if (cast(E)->getOperatorLoc().isMacroID()) + return true; + Fixes.push_back( + FixItHint::CreateRemoval(cast(E)->getOperatorLoc())); + return false; + } + if (const auto *BinOp = dyn_cast(E)) { + return flipDemorganBinaryOperator(Fixes, Ctx, BinOp, OuterBO); + } + if (const auto *Paren = dyn_cast(E)) { + if (const auto *BinOp = dyn_cast(Paren->getSubExpr())) { + return flipDemorganBinaryOperator(Fixes, Ctx, BinOp, OuterBO, Paren); + } + } + // Fallback case just insert a logical not operator. + if (E->getBeginLoc().isMacroID()) + return true; + Fixes.push_back(FixItHint::CreateInsertion(E->getBeginLoc(), "!")); + return false; +} + +static bool shouldRemoveParens(const Stmt *Parent, + BinaryOperatorKind NewOuterBinary, + const ParenExpr *Parens) { + if (!Parens) + return false; + if (!Parent) + return true; + switch (Parent->getStmtClass()) { + case Stmt::BinaryOperatorClass: { + const auto *BO = cast(Parent); + if (BO->isAssignmentOp()) + return true; + if (BO->isCommaOp()) + return true; + if (BO->getOpcode() == NewOuterBinary) + return true; + return false; + } + case Stmt::UnaryOperatorClass: + case Stmt::CXXRewrittenBinaryOperatorClass: + return false; + default: + return true; + } +} + +bool SimplifyBooleanExprCheck::reportDeMorgan(const ASTContext &Context, + const UnaryOperator *Outer, + const BinaryOperator *Inner, + bool TryOfferFix, + const Stmt *Parent, + const ParenExpr *Parens) { + assert(Outer); + assert(Inner); + assert(Inner->isLogicalOp()); + + 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 (!TryOfferFix) + return false; + if (Outer->getOperatorLoc().isMacroID()) + return false; + SmallVector Fixes; + auto NewOpcode = getDemorganFlippedOperator(Inner->getOpcode()); + if (shouldRemoveParens(Parent, NewOpcode, Parens)) { + Fixes.push_back(FixItHint::CreateRemoval( + SourceRange(Outer->getOperatorLoc(), Parens->getLParen()))); + Fixes.push_back(FixItHint::CreateRemoval(Parens->getRParen())); + } else { + Fixes.push_back(FixItHint::CreateRemoval(Outer->getOperatorLoc())); + } + if (flipDemorganOperator(Fixes, Inner)) + return false; + if (flipDemorganSide(Fixes, Context, Inner->getLHS(), NewOpcode) || + flipDemorganSide(Fixes, Context, Inner->getRHS(), NewOpcode)) + return false; + Diag << Fixes; + return true; +} } // namespace readability } // namespace tidy } // namespace clang diff --git a/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.h b/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.h index 2724c9a..72d8f33 100644 --- a/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.h +++ b/clang-tools-extra/clang-tidy/readability/SimplifyBooleanExprCheck.h @@ -58,12 +58,17 @@ private: const IfStmt *If, const Expr *ThenReturn); + bool reportDeMorgan(const ASTContext &Context, const UnaryOperator *Outer, + const BinaryOperator *Inner, bool TryOfferFix, + const Stmt *Parent, const ParenExpr *Parens); + void issueDiag(const ASTContext &Result, SourceLocation Loc, StringRef Description, SourceRange ReplacementRange, StringRef Replacement); const bool ChainedConditionalReturn; const bool ChainedConditionalAssignment; + const bool SimplifyDeMorgan; }; } // namespace readability diff --git a/clang-tools-extra/docs/ReleaseNotes.rst b/clang-tools-extra/docs/ReleaseNotes.rst index 41a9723..74e77f4 100644 --- a/clang-tools-extra/docs/ReleaseNotes.rst +++ b/clang-tools-extra/docs/ReleaseNotes.rst @@ -194,6 +194,10 @@ Changes in existing checks ` when the parameter is referenced by an lvalue. +- Expanded :doc:`readability-simplify-boolean-expr + ` to simplify expressions + using DeMorgan's Theorem. + Removed checks ^^^^^^^^^^^^^^ 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 index ef28acd..240e7be 100644 --- 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 @@ 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: @@ -27,6 +28,12 @@ Initial expression Result ``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 @@ Options 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 index 0000000..12a9eb6 --- /dev/null +++ b/clang-tools-extra/test/clang-tidy/checkers/readability-simplify-bool-expr-demorgan.cpp @@ -0,0 +1,87 @@ +// RUN: %check_clang_tidy %s readability-simplify-boolean-expr %t + +void eat(bool); + +void foo(bool A1, bool A2, bool A3, bool A4) { + 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); + + // Testing to see how it handles parens + X = !(A1 && !A2 && !A3); + X = !(A1 && !A2 || !A3); + X = !(!A1 || A2 && !A3); + X = !((A1 || !A2) && !A3); + X = !((A1 || !A2) || !A3); + // CHECK-MESSAGES: :[[@LINE-5]]:7: warning: boolean expression can be simplified by DeMorgan's theorem + // CHECK-MESSAGES: :[[@LINE-5]]:7: warning: boolean expression can be simplified by DeMorgan's theorem + // CHECK-MESSAGES: :[[@LINE-5]]:7: warning: boolean expression can be simplified by DeMorgan's theorem + // CHECK-MESSAGES: :[[@LINE-5]]:7: warning: boolean expression can be simplified by DeMorgan's theorem + // CHECK-MESSAGES: :[[@LINE-5]]: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); + // CHECK-FIXES-NEXT: X = (!A1 && A2) || A3; + // CHECK-FIXES-NEXT: X = !A1 && A2 && A3; + X = !((A1 || A2) && (!A3 || A4)); + // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: boolean expression can be simplified by DeMorgan's theorem + // CHECK-FIXES: X = (!A1 && !A2) || (A3 && !A4); + + eat(!(!A1 && !A2)); + // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: boolean expression can be simplified by DeMorgan's theorem + // CHECK-FIXES: eat(A1 || A2); + + bool Init = !(!A1 || !A2); + // CHECK-MESSAGES: :[[@LINE-1]]:15: warning: boolean expression can be simplified by DeMorgan's theorem + // CHECK-FIXES: bool Init = A1 && A2; + + X = A1 && !(!A2 || !A3); + X = A1 || !(!A2 || !A3); + X = A1 && !(!A2 && !A3); + // CHECK-MESSAGES: :[[@LINE-3]]:13: warning: boolean expression can be simplified by DeMorgan's theorem + // CHECK-MESSAGES: :[[@LINE-3]]:13: warning: boolean expression can be simplified by DeMorgan's theorem + // CHECK-MESSAGES: :[[@LINE-3]]:13: 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); +} -- 2.7.4