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 @@ -57,12 +57,16 @@ const ReturnStmt *Ret, bool Negated, const IfStmt *If); + bool reportDeMorgan(const ASTContext &Context, const UnaryOperator *Outer, + const BinaryOperator *Inner, bool TryOfferFix); + 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/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 @@ -9,6 +9,7 @@ #include "SimplifyBooleanExprCheck.h" #include "clang/AST/RecursiveASTVisitor.h" #include "clang/Lex/Lexer.h" +#include "llvm/Support/SaveAndRestore.h" #include #include @@ -292,6 +293,8 @@ } class SimplifyBooleanExprCheck::Visitor : public RecursiveASTVisitor { + using Base = RecursiveASTVisitor; + public: Visitor(SimplifyBooleanExprCheck *Check, ASTContext &Context) : Check(Check), Context(Context) {} @@ -531,7 +534,67 @@ 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); + const auto *Sub = dyn_cast( + Op->getSubExpr()->IgnoreUnlessSpelledInSource()); + if (!Sub || !Sub->isLogicalOp() || !Sub->getType()->isBooleanType()) + return Base::TraverseUnaryOperator(Op); + if (checkEitherSide(Sub, isUnaryLNot) || + checkEitherSide(Sub, + [](const Expr *E) { return nestedDemorgan(E, 1); })) { + if (Check->reportDeMorgan(Context, Op, Sub, !IsProcessing) && + !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; @@ -542,7 +605,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) @@ -713,6 +777,162 @@ 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; +} + +bool SimplifyBooleanExprCheck::reportDeMorgan(const ASTContext &Context, + const UnaryOperator *Outer, + const BinaryOperator *Inner, + bool TryOfferFix) { + 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; + Fixes.push_back(FixItHint::CreateRemoval(Outer->getOperatorLoc())); + if (flipDemorganOperator(Fixes, Inner)) + return false; + auto NewOpcode = getDemorganFlippedOperator(Inner->getOpcode()); + 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/docs/ReleaseNotes.rst b/clang-tools-extra/docs/ReleaseNotes.rst --- a/clang-tools-extra/docs/ReleaseNotes.rst +++ b/clang-tools-extra/docs/ReleaseNotes.rst @@ -185,6 +185,10 @@ ` 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 --- 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,67 @@ +// RUN: %check_clang_tidy %s readability-simplify-boolean-expr %t + +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)); +}