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 @@ -98,12 +98,16 @@ void replaceLabelCompoundReturnWithCondition( const ast_matchers::MatchFinder::MatchResult &Result, bool Negated); + bool reportDeMorgan(const ASTContext &Context, const UnaryOperator *Outer, + const BinaryOperator *Inner, bool TryOfferFix); + 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 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,7 @@ #include "SimplifyBooleanExprMatchers.h" #include "clang/AST/RecursiveASTVisitor.h" #include "clang/Lex/Lexer.h" +#include "llvm/Support/SaveAndRestore.h" #include #include @@ -61,6 +62,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"; @@ -351,6 +354,8 @@ } class SimplifyBooleanExprCheck::Visitor : public RecursiveASTVisitor { + using Base = RecursiveASTVisitor; + public: Visitor(SimplifyBooleanExprCheck *Check, const MatchFinder::MatchResult &Result) @@ -361,7 +366,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(*Result.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; const MatchFinder::MatchResult &Result; }; @@ -371,7 +436,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) @@ -787,6 +853,159 @@ 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 BinaryOperatorKind getDemorganFlippedOperator(BinaryOperatorKind BO) { + assert(BO == BO_LAnd || BO == BO_LOr); + return BO == BO_LAnd ? BO_LOr : BO_LAnd; +} + +namespace { +struct DmFixesInfo { + const ASTContext &Ctx; + llvm::SmallVector Fixes = {}; +}; +} // namespace + +static bool flipDemorganSide(DmFixesInfo &Fix, const Expr *E, + Optional OuterBO); + +static SourceLocation getEndOfTok(const ASTContext &Context, + SourceLocation Loc) { + return Loc.getLocWithOffset(Lexer::MeasureTokenLength( + Loc, Context.getSourceManager(), Context.getLangOpts())); +} + +static bool flipDemorganBinaryOperator(DmFixesInfo &Fix, + 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(Fix.Fixes, BinOp)) + return true; + auto NewOp = getDemorganFlippedOperator(BinOp->getOpcode()); + if (OuterBO) { + if (((*OuterBO == NewOp) || (*OuterBO == BO_LOr && NewOp == BO_LAnd)) && + Parens) { + if (!Parens->getLParen().isMacroID() && + !Parens->getRParen().isMacroID()) { + Fix.Fixes.push_back(FixItHint::CreateRemoval(Parens->getLParen())); + Fix.Fixes.push_back(FixItHint::CreateRemoval(Parens->getRParen())); + } + } + if (*OuterBO == BO_LAnd && NewOp == BO_LOr && !Parens) { + Fix.Fixes.push_back( + FixItHint::CreateInsertion(BinOp->getBeginLoc(), "(")); + Fix.Fixes.push_back(FixItHint::CreateInsertion( + getEndOfTok(Fix.Ctx, BinOp->getEndLoc()), ")")); + } + } + if (flipDemorganSide(Fix, BinOp->getLHS(), NewOp) || + flipDemorganSide(Fix, 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; + Fix.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; + Fix.Fixes.push_back( + FixItHint::CreateInsertion(Parens->getBeginLoc(), "!")); + } else { + if (BinOp->getBeginLoc().isMacroID() || BinOp->getEndLoc().isMacroID()) + return true; + Fix.Fixes.append({FixItHint::CreateInsertion(BinOp->getBeginLoc(), "!("), + FixItHint::CreateInsertion( + getEndOfTok(Fix.Ctx, BinOp->getEndLoc()), ")")}); + } + break; + } + return false; +} + +static bool flipDemorganSide(DmFixesInfo &Fix, 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; + Fix.Fixes.push_back( + FixItHint::CreateRemoval(cast(E)->getOperatorLoc())); + return false; + } + if (const auto *BinOp = dyn_cast(E)) { + return flipDemorganBinaryOperator(Fix, BinOp, OuterBO); + } + if (const auto *Paren = dyn_cast(E)) { + if (const auto *BinOp = dyn_cast(Paren->getSubExpr())) { + return flipDemorganBinaryOperator(Fix, BinOp, OuterBO, Paren); + } + } + // Fallback case just insert a logical not operator. + if (E->getBeginLoc().isMacroID()) + return true; + Fix.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->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 (!TryOfferFix) + return false; + if (Outer->getOperatorLoc().isMacroID()) + return false; + DmFixesInfo Fix{Context}; + Fix.Fixes.push_back(FixItHint::CreateRemoval(Outer->getOperatorLoc())); + if (flipDemorganOperator(Fix.Fixes, Inner)) + return false; + auto NewOperator = getDemorganFlippedOperator(Inner->getOpcode()); + if (flipDemorganSide(Fix, Inner->getLHS(), NewOperator)) + return false; + if (flipDemorganSide(Fix, Inner->getRHS(), NewOperator)) + return false; + Diag << Fix.Fixes; + return true; +} } // 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,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); +}