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

   1 //===-- SimplifyBooleanExprCheck.cpp - clang-tidy -------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "SimplifyBooleanExprCheck.h"
  10 #include "clang/AST/RecursiveASTVisitor.h"
  11 #include "clang/Lex/Lexer.h"
  12 #include "llvm/Support/SaveAndRestore.h"
  13
  14 #include <optional>
  15 #include <string>
  16 #include <utility>
  17
  18 using namespace clang::ast_matchers;
  19
  20 namespace clang::tidy::readability {
  21
  22 namespace {
  23
  24 StringRef getText(const ASTContext &Context, SourceRange Range) {
  25   return Lexer::getSourceText(CharSourceRange::getTokenRange(Range),
  26                               Context.getSourceManager(),
  27                               Context.getLangOpts());
  28 }
  29
  30 template <typename T> StringRef getText(const ASTContext &Context, T &Node) {
  31   return getText(Context, Node.getSourceRange());
  32 }
  33
  34 } // namespace
  35
  36 static constexpr char SimplifyOperatorDiagnostic[] =
  37     "redundant boolean literal supplied to boolean operator";
  38 static constexpr char SimplifyConditionDiagnostic[] =
  39     "redundant boolean literal in if statement condition";
  40 static constexpr char SimplifyConditionalReturnDiagnostic[] =
  41     "redundant boolean literal in conditional return statement";
  42
  43 static bool needsParensAfterUnaryNegation(const Expr *E) {
  44   E = E->IgnoreImpCasts();
  45   if (isa<BinaryOperator>(E) || isa<ConditionalOperator>(E))
  46     return true;
  47
  48   if (const auto *Op = dyn_cast<CXXOperatorCallExpr>(E))
  49     return Op->getNumArgs() == 2 && Op->getOperator() != OO_Call &&
  50            Op->getOperator() != OO_Subscript;
  51
  52   return false;
  53 }
  54
  55 static std::pair<BinaryOperatorKind, BinaryOperatorKind> Opposites[] = {
  56     {BO_LT, BO_GE}, {BO_GT, BO_LE}, {BO_EQ, BO_NE}};
  57
  58 static StringRef negatedOperator(const BinaryOperator *BinOp) {
  59   const BinaryOperatorKind Opcode = BinOp->getOpcode();
  60   for (auto NegatableOp : Opposites) {
  61     if (Opcode == NegatableOp.first)
  62       return BinaryOperator::getOpcodeStr(NegatableOp.second);
  63     if (Opcode == NegatableOp.second)
  64       return BinaryOperator::getOpcodeStr(NegatableOp.first);
  65   }
  66   return {};
  67 }
  68
  69 static std::pair<OverloadedOperatorKind, StringRef> OperatorNames[] = {
  70     {OO_EqualEqual, "=="},   {OO_ExclaimEqual, "!="}, {OO_Less, "<"},
  71     {OO_GreaterEqual, ">="}, {OO_Greater, ">"},       {OO_LessEqual, "<="}};
  72
  73 static StringRef getOperatorName(OverloadedOperatorKind OpKind) {
  74   for (auto Name : OperatorNames) {
  75     if (Name.first == OpKind)
  76       return Name.second;
  77   }
  78
  79   return {};
  80 }
  81
  82 static std::pair<OverloadedOperatorKind, OverloadedOperatorKind>
  83     OppositeOverloads[] = {{OO_EqualEqual, OO_ExclaimEqual},
  84                            {OO_Less, OO_GreaterEqual},
  85                            {OO_Greater, OO_LessEqual}};
  86
  87 static StringRef negatedOperator(const CXXOperatorCallExpr *OpCall) {
  88   const OverloadedOperatorKind Opcode = OpCall->getOperator();
  89   for (auto NegatableOp : OppositeOverloads) {
  90     if (Opcode == NegatableOp.first)
  91       return getOperatorName(NegatableOp.second);
  92     if (Opcode == NegatableOp.second)
  93       return getOperatorName(NegatableOp.first);
  94   }
  95   return {};
  96 }
  97
  98 static std::string asBool(StringRef Text, bool NeedsStaticCast) {
  99   if (NeedsStaticCast)
 100     return ("static_cast<bool>(" + Text + ")").str();
 101
 102   return std::string(Text);
 103 }
 104
 105 static bool needsNullPtrComparison(const Expr *E) {
 106   if (const auto *ImpCast = dyn_cast<ImplicitCastExpr>(E))
 107     return ImpCast->getCastKind() == CK_PointerToBoolean ||
 108            ImpCast->getCastKind() == CK_MemberPointerToBoolean;
 109
 110   return false;
 111 }
 112
 113 static bool needsZeroComparison(const Expr *E) {
 114   if (const auto *ImpCast = dyn_cast<ImplicitCastExpr>(E))
 115     return ImpCast->getCastKind() == CK_IntegralToBoolean;
 116
 117   return false;
 118 }
 119
 120 static bool needsStaticCast(const Expr *E) {
 121   if (const auto *ImpCast = dyn_cast<ImplicitCastExpr>(E)) {
 122     if (ImpCast->getCastKind() == CK_UserDefinedConversion &&
 123         ImpCast->getSubExpr()->getType()->isBooleanType()) {
 124       if (const auto *MemCall =
 125               dyn_cast<CXXMemberCallExpr>(ImpCast->getSubExpr())) {
 126         if (const auto *MemDecl =
 127                 dyn_cast<CXXConversionDecl>(MemCall->getMethodDecl())) {
 128           if (MemDecl->isExplicit())
 129             return true;
 130         }
 131       }
 132     }
 133   }
 134
 135   E = E->IgnoreImpCasts();
 136   return !E->getType()->isBooleanType();
 137 }
 138
 139 static std::string compareExpressionToConstant(const ASTContext &Context,
 140                                                const Expr *E, bool Negated,
 141                                                const char *Constant) {
 142   E = E->IgnoreImpCasts();
 143   const std::string ExprText =
 144       (isa<BinaryOperator>(E) ? ("(" + getText(Context, *E) + ")")
 145                               : getText(Context, *E))
 146           .str();
 147   return ExprText + " " + (Negated ? "!=" : "==") + " " + Constant;
 148 }
 149
 150 static std::string compareExpressionToNullPtr(const ASTContext &Context,
 151                                               const Expr *E, bool Negated) {
 152   const char *NullPtr = Context.getLangOpts().CPlusPlus11 ? "nullptr" : "NULL";
 153   return compareExpressionToConstant(Context, E, Negated, NullPtr);
 154 }
 155
 156 static std::string compareExpressionToZero(const ASTContext &Context,
 157                                            const Expr *E, bool Negated) {
 158   return compareExpressionToConstant(Context, E, Negated, "0");
 159 }
 160
 161 static std::string replacementExpression(const ASTContext &Context,
 162                                          bool Negated, const Expr *E) {
 163   E = E->IgnoreParenBaseCasts();
 164   if (const auto *EC = dyn_cast<ExprWithCleanups>(E))
 165     E = EC->getSubExpr();
 166
 167   const bool NeedsStaticCast = needsStaticCast(E);
 168   if (Negated) {
 169     if (const auto *UnOp = dyn_cast<UnaryOperator>(E)) {
 170       if (UnOp->getOpcode() == UO_LNot) {
 171         if (needsNullPtrComparison(UnOp->getSubExpr()))
 172           return compareExpressionToNullPtr(Context, UnOp->getSubExpr(), true);
 173
 174         if (needsZeroComparison(UnOp->getSubExpr()))
 175           return compareExpressionToZero(Context, UnOp->getSubExpr(), true);
 176
 177         return replacementExpression(Context, false, UnOp->getSubExpr());
 178       }
 179     }
 180
 181     if (needsNullPtrComparison(E))
 182       return compareExpressionToNullPtr(Context, E, false);
 183
 184     if (needsZeroComparison(E))
 185       return compareExpressionToZero(Context, E, false);
 186
 187     StringRef NegatedOperator;
 188     const Expr *LHS = nullptr;
 189     const Expr *RHS = nullptr;
 190     if (const auto *BinOp = dyn_cast<BinaryOperator>(E)) {
 191       NegatedOperator = negatedOperator(BinOp);
 192       LHS = BinOp->getLHS();
 193       RHS = BinOp->getRHS();
 194     } else if (const auto *OpExpr = dyn_cast<CXXOperatorCallExpr>(E)) {
 195       if (OpExpr->getNumArgs() == 2) {
 196         NegatedOperator = negatedOperator(OpExpr);
 197         LHS = OpExpr->getArg(0);
 198         RHS = OpExpr->getArg(1);
 199       }
 200     }
 201     if (!NegatedOperator.empty() && LHS && RHS)
 202       return (asBool((getText(Context, *LHS) + " " + NegatedOperator + " " +
 203                       getText(Context, *RHS))
 204                          .str(),
 205                      NeedsStaticCast));
 206
 207     StringRef Text = getText(Context, *E);
 208     if (!NeedsStaticCast && needsParensAfterUnaryNegation(E))
 209       return ("!(" + Text + ")").str();
 210
 211     if (needsNullPtrComparison(E))
 212       return compareExpressionToNullPtr(Context, E, false);
 213
 214     if (needsZeroComparison(E))
 215       return compareExpressionToZero(Context, E, false);
 216
 217     return ("!" + asBool(Text, NeedsStaticCast));
 218   }
 219
 220   if (const auto *UnOp = dyn_cast<UnaryOperator>(E)) {
 221     if (UnOp->getOpcode() == UO_LNot) {
 222       if (needsNullPtrComparison(UnOp->getSubExpr()))
 223         return compareExpressionToNullPtr(Context, UnOp->getSubExpr(), false);
 224
 225       if (needsZeroComparison(UnOp->getSubExpr()))
 226         return compareExpressionToZero(Context, UnOp->getSubExpr(), false);
 227     }
 228   }
 229
 230   if (needsNullPtrComparison(E))
 231     return compareExpressionToNullPtr(Context, E, true);
 232
 233   if (needsZeroComparison(E))
 234     return compareExpressionToZero(Context, E, true);
 235
 236   return asBool(getText(Context, *E), NeedsStaticCast);
 237 }
 238
 239 static bool containsDiscardedTokens(const ASTContext &Context,
 240                                     CharSourceRange CharRange) {
 241   std::string ReplacementText =
 242       Lexer::getSourceText(CharRange, Context.getSourceManager(),
 243                            Context.getLangOpts())
 244           .str();
 245   Lexer Lex(CharRange.getBegin(), Context.getLangOpts(), ReplacementText.data(),
 246             ReplacementText.data(),
 247             ReplacementText.data() + ReplacementText.size());
 248   Lex.SetCommentRetentionState(true);
 249
 250   Token Tok;
 251   while (!Lex.LexFromRawLexer(Tok)) {
 252     if (Tok.is(tok::TokenKind::comment) || Tok.is(tok::TokenKind::hash))
 253       return true;
 254   }
 255
 256   return false;
 257 }
 258
 259 class SimplifyBooleanExprCheck::Visitor : public RecursiveASTVisitor<Visitor> {
 260   using Base = RecursiveASTVisitor<Visitor>;
 261
 262 public:
 263   Visitor(SimplifyBooleanExprCheck *Check, ASTContext &Context)
 264       : Check(Check), Context(Context) {}
 265
 266   bool traverse() { return TraverseAST(Context); }
 267
 268   static bool shouldIgnore(Stmt *S) {
 269     switch (S->getStmtClass()) {
 270     case Stmt::ImplicitCastExprClass:
 271     case Stmt::MaterializeTemporaryExprClass:
 272     case Stmt::CXXBindTemporaryExprClass:
 273       return true;
 274     default:
 275       return false;
 276     }
 277   }
 278
 279   bool dataTraverseStmtPre(Stmt *S) {
 280     if (S && !shouldIgnore(S))
 281       StmtStack.push_back(S);
 282     return true;
 283   }
 284
 285   bool dataTraverseStmtPost(Stmt *S) {
 286     if (S && !shouldIgnore(S)) {
 287       assert(StmtStack.back() == S);
 288       StmtStack.pop_back();
 289     }
 290     return true;
 291   }
 292
 293   bool VisitBinaryOperator(const BinaryOperator *Op) const {
 294     Check->reportBinOp(Context, Op);
 295     return true;
 296   }
 297
 298   // Extracts a bool if an expression is (true|false|!true|!false);
 299   static std::optional<bool> getAsBoolLiteral(const Expr *E, bool FilterMacro) {
 300     if (const auto *Bool = dyn_cast<CXXBoolLiteralExpr>(E)) {
 301       if (FilterMacro && Bool->getBeginLoc().isMacroID())
 302         return std::nullopt;
 303       return Bool->getValue();
 304     }
 305     if (const auto *UnaryOp = dyn_cast<UnaryOperator>(E)) {
 306       if (FilterMacro && UnaryOp->getBeginLoc().isMacroID())
 307         return std::nullopt;
 308       if (UnaryOp->getOpcode() == UO_LNot)
 309         if (std::optional<bool> Res = getAsBoolLiteral(
 310                 UnaryOp->getSubExpr()->IgnoreImplicit(), FilterMacro))
 311           return !*Res;
 312     }
 313     return std::nullopt;
 314   }
 315
 316   template <typename Node> struct NodeAndBool {
 317     const Node *Item = nullptr;
 318     bool Bool = false;
 319
 320     operator bool() const { return Item != nullptr; }
 321   };
 322
 323   using ExprAndBool = NodeAndBool<Expr>;
 324   using DeclAndBool = NodeAndBool<Decl>;
 325
 326   /// Detect's return (true|false|!true|!false);
 327   static ExprAndBool parseReturnLiteralBool(const Stmt *S) {
 328     const auto *RS = dyn_cast<ReturnStmt>(S);
 329     if (!RS || !RS->getRetValue())
 330       return {};
 331     if (std::optional<bool> Ret =
 332             getAsBoolLiteral(RS->getRetValue()->IgnoreImplicit(), false)) {
 333       return {RS->getRetValue(), *Ret};
 334     }
 335     return {};
 336   }
 337
 338   /// If \p S is not a \c CompoundStmt, applies F on \p S, otherwise if there is
 339   /// only 1 statement in the \c CompoundStmt, applies F on that single
 340   /// statement.
 341   template <typename Functor>
 342   static auto checkSingleStatement(Stmt *S, Functor F) -> decltype(F(S)) {
 343     if (auto *CS = dyn_cast<CompoundStmt>(S)) {
 344       if (CS->size() == 1)
 345         return F(CS->body_front());
 346       return {};
 347     }
 348     return F(S);
 349   }
 350
 351   Stmt *parent() const {
 352     return StmtStack.size() < 2 ? nullptr : StmtStack[StmtStack.size() - 2];
 353   }
 354
 355   bool VisitIfStmt(IfStmt *If) {
 356     // Skip any if's that have a condition var or an init statement, or are
 357     // "if consteval" statements.
 358     if (If->hasInitStorage() || If->hasVarStorage() || If->isConsteval())
 359       return true;
 360     /*
 361      * if (true) ThenStmt(); -> ThenStmt();
 362      * if (false) ThenStmt(); -> <Empty>;
 363      * if (false) ThenStmt(); else ElseStmt() -> ElseStmt();
 364      */
 365     Expr *Cond = If->getCond()->IgnoreImplicit();
 366     if (std::optional<bool> Bool = getAsBoolLiteral(Cond, true)) {
 367       if (*Bool)
 368         Check->replaceWithThenStatement(Context, If, Cond);
 369       else
 370         Check->replaceWithElseStatement(Context, If, Cond);
 371     }
 372
 373     if (If->getElse()) {
 374       /*
 375        * if (Cond) return true; else return false; -> return Cond;
 376        * if (Cond) return false; else return true; -> return !Cond;
 377        */
 378       if (ExprAndBool ThenReturnBool =
 379               checkSingleStatement(If->getThen(), parseReturnLiteralBool)) {
 380         ExprAndBool ElseReturnBool =
 381             checkSingleStatement(If->getElse(), parseReturnLiteralBool);
 382         if (ElseReturnBool && ThenReturnBool.Bool != ElseReturnBool.Bool) {
 383           if (Check->ChainedConditionalReturn ||
 384               !isa_and_nonnull<IfStmt>(parent())) {
 385             Check->replaceWithReturnCondition(Context, If, ThenReturnBool.Item,
 386                                               ElseReturnBool.Bool);
 387           }
 388         }
 389       } else {
 390         /*
 391          * if (Cond) A = true; else A = false; -> A = Cond;
 392          * if (Cond) A = false; else A = true; -> A = !Cond;
 393          */
 394         Expr *Var = nullptr;
 395         SourceLocation Loc;
 396         auto VarBoolAssignmentMatcher = [&Var,
 397                                          &Loc](const Stmt *S) -> DeclAndBool {
 398           const auto *BO = dyn_cast<BinaryOperator>(S);
 399           if (!BO || BO->getOpcode() != BO_Assign)
 400             return {};
 401           std::optional<bool> RightasBool =
 402               getAsBoolLiteral(BO->getRHS()->IgnoreImplicit(), false);
 403           if (!RightasBool)
 404             return {};
 405           Expr *IgnImp = BO->getLHS()->IgnoreImplicit();
 406           if (!Var) {
 407             // We only need to track these for the Then branch.
 408             Loc = BO->getRHS()->getBeginLoc();
 409             Var = IgnImp;
 410           }
 411           if (auto *DRE = dyn_cast<DeclRefExpr>(IgnImp))
 412             return {DRE->getDecl(), *RightasBool};
 413           if (auto *ME = dyn_cast<MemberExpr>(IgnImp))
 414             return {ME->getMemberDecl(), *RightasBool};
 415           return {};
 416         };
 417         if (DeclAndBool ThenAssignment =
 418                 checkSingleStatement(If->getThen(), VarBoolAssignmentMatcher)) {
 419           DeclAndBool ElseAssignment =
 420               checkSingleStatement(If->getElse(), VarBoolAssignmentMatcher);
 421           if (ElseAssignment.Item == ThenAssignment.Item &&
 422               ElseAssignment.Bool != ThenAssignment.Bool) {
 423             if (Check->ChainedConditionalAssignment ||
 424                 !isa_and_nonnull<IfStmt>(parent())) {
 425               Check->replaceWithAssignment(Context, If, Var, Loc,
 426                                            ElseAssignment.Bool);
 427             }
 428           }
 429         }
 430       }
 431     }
 432     return true;
 433   }
 434
 435   bool VisitConditionalOperator(ConditionalOperator *Cond) {
 436     /*
 437      * Condition ? true : false; -> Condition
 438      * Condition ? false : true; -> !Condition;
 439      */
 440     if (std::optional<bool> Then =
 441             getAsBoolLiteral(Cond->getTrueExpr()->IgnoreImplicit(), false)) {
 442       if (std::optional<bool> Else =
 443               getAsBoolLiteral(Cond->getFalseExpr()->IgnoreImplicit(), false)) {
 444         if (*Then != *Else)
 445           Check->replaceWithCondition(Context, Cond, *Else);
 446       }
 447     }
 448     return true;
 449   }
 450
 451   bool VisitCompoundStmt(CompoundStmt *CS) {
 452     if (CS->size() < 2)
 453       return true;
 454     bool CurIf = false, PrevIf = false;
 455     for (auto First = CS->body_begin(), Second = std::next(First),
 456               End = CS->body_end();
 457          Second != End; ++Second, ++First) {
 458       PrevIf = CurIf;
 459       CurIf = isa<IfStmt>(*First);
 460       ExprAndBool TrailingReturnBool = parseReturnLiteralBool(*Second);
 461       if (!TrailingReturnBool)
 462         continue;
 463
 464       if (CurIf) {
 465         /*
 466          * if (Cond) return true; return false; -> return Cond;
 467          * if (Cond) return false; return true; -> return !Cond;
 468          */
 469         auto *If = cast<IfStmt>(*First);
 470         if (!If->hasInitStorage() && !If->hasVarStorage() &&
 471             !If->isConsteval()) {
 472           ExprAndBool ThenReturnBool =
 473               checkSingleStatement(If->getThen(), parseReturnLiteralBool);
 474           if (ThenReturnBool &&
 475               ThenReturnBool.Bool != TrailingReturnBool.Bool) {
 476             if ((Check->ChainedConditionalReturn || !PrevIf) &&
 477                 If->getElse() == nullptr) {
 478               Check->replaceCompoundReturnWithCondition(
 479                   Context, cast<ReturnStmt>(*Second), TrailingReturnBool.Bool,
 480                   If, ThenReturnBool.Item);
 481             }
 482           }
 483         }
 484       } else if (isa<LabelStmt, CaseStmt, DefaultStmt>(*First)) {
 485         /*
 486          * (case X|label_X|default): if (Cond) return BoolLiteral;
 487          *                           return !BoolLiteral
 488          */
 489         Stmt *SubStmt =
 490             isa<LabelStmt>(*First)  ? cast<LabelStmt>(*First)->getSubStmt()
 491             : isa<CaseStmt>(*First) ? cast<CaseStmt>(*First)->getSubStmt()
 492                                     : cast<DefaultStmt>(*First)->getSubStmt();
 493         auto *SubIf = dyn_cast<IfStmt>(SubStmt);
 494         if (SubIf && !SubIf->getElse() && !SubIf->hasInitStorage() &&
 495             !SubIf->hasVarStorage() && !SubIf->isConsteval()) {
 496           ExprAndBool ThenReturnBool =
 497               checkSingleStatement(SubIf->getThen(), parseReturnLiteralBool);
 498           if (ThenReturnBool &&
 499               ThenReturnBool.Bool != TrailingReturnBool.Bool) {
 500             Check->replaceCompoundReturnWithCondition(
 501                 Context, cast<ReturnStmt>(*Second), TrailingReturnBool.Bool,
 502                 SubIf, ThenReturnBool.Item);
 503           }
 504         }
 505       }
 506     }
 507     return true;
 508   }
 509
 510   static bool isUnaryLNot(const Expr *E) {
 511     return isa<UnaryOperator>(E) &&
 512            cast<UnaryOperator>(E)->getOpcode() == UO_LNot;
 513   }
 514
 515   template <typename Functor>
 516   static bool checkEitherSide(const BinaryOperator *BO, Functor Func) {
 517     return Func(BO->getLHS()) || Func(BO->getRHS());
 518   }
 519
 520   static bool nestedDemorgan(const Expr *E, unsigned NestingLevel) {
 521     const auto *BO = dyn_cast<BinaryOperator>(E->IgnoreUnlessSpelledInSource());
 522     if (!BO)
 523       return false;
 524     if (!BO->getType()->isBooleanType())
 525       return false;
 526     switch (BO->getOpcode()) {
 527     case BO_LT:
 528     case BO_GT:
 529     case BO_LE:
 530     case BO_GE:
 531     case BO_EQ:
 532     case BO_NE:
 533       return true;
 534     case BO_LAnd:
 535     case BO_LOr:
 536       if (checkEitherSide(BO, isUnaryLNot))
 537         return true;
 538       if (NestingLevel) {
 539         if (checkEitherSide(BO, [NestingLevel](const Expr *E) {
 540               return nestedDemorgan(E, NestingLevel - 1);
 541             }))
 542           return true;
 543       }
 544       return false;
 545     default:
 546       return false;
 547     }
 548   }
 549
 550   bool TraverseUnaryOperator(UnaryOperator *Op) {
 551     if (!Check->SimplifyDeMorgan || Op->getOpcode() != UO_LNot)
 552       return Base::TraverseUnaryOperator(Op);
 553     Expr *SubImp = Op->getSubExpr()->IgnoreImplicit();
 554     auto *Parens = dyn_cast<ParenExpr>(SubImp);
 555     auto *BinaryOp =
 556         Parens
 557             ? dyn_cast<BinaryOperator>(Parens->getSubExpr()->IgnoreImplicit())
 558             : dyn_cast<BinaryOperator>(SubImp);
 559     if (!BinaryOp || !BinaryOp->isLogicalOp() ||
 560         !BinaryOp->getType()->isBooleanType())
 561       return Base::TraverseUnaryOperator(Op);
 562     if (Check->SimplifyDeMorganRelaxed ||
 563         checkEitherSide(BinaryOp, isUnaryLNot) ||
 564         checkEitherSide(BinaryOp,
 565                         [](const Expr *E) { return nestedDemorgan(E, 1); })) {
 566       if (Check->reportDeMorgan(Context, Op, BinaryOp, !IsProcessing, parent(),
 567                                 Parens) &&
 568           !Check->areDiagsSelfContained()) {
 569         llvm::SaveAndRestore RAII(IsProcessing, true);
 570         return Base::TraverseUnaryOperator(Op);
 571       }
 572     }
 573     return Base::TraverseUnaryOperator(Op);
 574   }
 575
 576 private:
 577   bool IsProcessing = false;
 578   SimplifyBooleanExprCheck *Check;
 579   SmallVector<Stmt *, 32> StmtStack;
 580   ASTContext &Context;
 581 };
 582
 583 SimplifyBooleanExprCheck::SimplifyBooleanExprCheck(StringRef Name,
 584                                                    ClangTidyContext *Context)
 585     : ClangTidyCheck(Name, Context),
 586       ChainedConditionalReturn(Options.get("ChainedConditionalReturn", false)),
 587       ChainedConditionalAssignment(
 588           Options.get("ChainedConditionalAssignment", false)),
 589       SimplifyDeMorgan(Options.get("SimplifyDeMorgan", true)),
 590       SimplifyDeMorganRelaxed(Options.get("SimplifyDeMorganRelaxed", false)) {
 591   if (SimplifyDeMorganRelaxed && !SimplifyDeMorgan)
 592     configurationDiag("%0: 'SimplifyDeMorganRelaxed' cannot be enabled "
 593                       "without 'SimplifyDeMorgan' enabled")
 594         << Name;
 595 }
 596
 597 static bool containsBoolLiteral(const Expr *E) {
 598   if (!E)
 599     return false;
 600   E = E->IgnoreParenImpCasts();
 601   if (isa<CXXBoolLiteralExpr>(E))
 602     return true;
 603   if (const auto *BinOp = dyn_cast<BinaryOperator>(E))
 604     return containsBoolLiteral(BinOp->getLHS()) ||
 605            containsBoolLiteral(BinOp->getRHS());
 606   if (const auto *UnaryOp = dyn_cast<UnaryOperator>(E))
 607     return containsBoolLiteral(UnaryOp->getSubExpr());
 608   return false;
 609 }
 610
 611 void SimplifyBooleanExprCheck::reportBinOp(const ASTContext &Context,
 612                                            const BinaryOperator *Op) {
 613   const auto *LHS = Op->getLHS()->IgnoreParenImpCasts();
 614   const auto *RHS = Op->getRHS()->IgnoreParenImpCasts();
 615
 616   const CXXBoolLiteralExpr *Bool = nullptr;
 617   const Expr *Other = nullptr;
 618   if ((Bool = dyn_cast<CXXBoolLiteralExpr>(LHS)) != nullptr)
 619     Other = RHS;
 620   else if ((Bool = dyn_cast<CXXBoolLiteralExpr>(RHS)) != nullptr)
 621     Other = LHS;
 622   else
 623     return;
 624
 625   if (Bool->getBeginLoc().isMacroID())
 626     return;
 627
 628   // FIXME: why do we need this?
 629   if (!isa<CXXBoolLiteralExpr>(Other) && containsBoolLiteral(Other))
 630     return;
 631
 632   bool BoolValue = Bool->getValue();
 633
 634   auto ReplaceWithExpression = [this, &Context, LHS, RHS,
 635                                 Bool](const Expr *ReplaceWith, bool Negated) {
 636     std::string Replacement =
 637         replacementExpression(Context, Negated, ReplaceWith);
 638     SourceRange Range(LHS->getBeginLoc(), RHS->getEndLoc());
 639     issueDiag(Context, Bool->getBeginLoc(), SimplifyOperatorDiagnostic, Range,
 640               Replacement);
 641   };
 642
 643   switch (Op->getOpcode()) {
 644   case BO_LAnd:
 645     if (BoolValue)
 646       // expr && true -> expr
 647       ReplaceWithExpression(Other, /*Negated=*/false);
 648     else
 649       // expr && false -> false
 650       ReplaceWithExpression(Bool, /*Negated=*/false);
 651     break;
 652   case BO_LOr:
 653     if (BoolValue)
 654       // expr || true -> true
 655       ReplaceWithExpression(Bool, /*Negated=*/false);
 656     else
 657       // expr || false -> expr
 658       ReplaceWithExpression(Other, /*Negated=*/false);
 659     break;
 660   case BO_EQ:
 661     // expr == true -> expr, expr == false -> !expr
 662     ReplaceWithExpression(Other, /*Negated=*/!BoolValue);
 663     break;
 664   case BO_NE:
 665     // expr != true -> !expr, expr != false -> expr
 666     ReplaceWithExpression(Other, /*Negated=*/BoolValue);
 667     break;
 668   default:
 669     break;
 670   }
 671 }
 672
 673 void SimplifyBooleanExprCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
 674   Options.store(Opts, "ChainedConditionalReturn", ChainedConditionalReturn);
 675   Options.store(Opts, "ChainedConditionalAssignment",
 676                 ChainedConditionalAssignment);
 677   Options.store(Opts, "SimplifyDeMorgan", SimplifyDeMorgan);
 678   Options.store(Opts, "SimplifyDeMorganRelaxed", SimplifyDeMorganRelaxed);
 679 }
 680
 681 void SimplifyBooleanExprCheck::registerMatchers(MatchFinder *Finder) {
 682   Finder->addMatcher(translationUnitDecl(), this);
 683 }
 684
 685 void SimplifyBooleanExprCheck::check(const MatchFinder::MatchResult &Result) {
 686   Visitor(this, *Result.Context).traverse();
 687 }
 688
 689 void SimplifyBooleanExprCheck::issueDiag(const ASTContext &Context,
 690                                          SourceLocation Loc,
 691                                          StringRef Description,
 692                                          SourceRange ReplacementRange,
 693                                          StringRef Replacement) {
 694   CharSourceRange CharRange =
 695       Lexer::makeFileCharRange(CharSourceRange::getTokenRange(ReplacementRange),
 696                                Context.getSourceManager(), getLangOpts());
 697
 698   DiagnosticBuilder Diag = diag(Loc, Description);
 699   if (!containsDiscardedTokens(Context, CharRange))
 700     Diag << FixItHint::CreateReplacement(CharRange, Replacement);
 701 }
 702
 703 void SimplifyBooleanExprCheck::replaceWithThenStatement(
 704     const ASTContext &Context, const IfStmt *IfStatement,
 705     const Expr *BoolLiteral) {
 706   issueDiag(Context, BoolLiteral->getBeginLoc(), SimplifyConditionDiagnostic,
 707             IfStatement->getSourceRange(),
 708             getText(Context, *IfStatement->getThen()));
 709 }
 710
 711 void SimplifyBooleanExprCheck::replaceWithElseStatement(
 712     const ASTContext &Context, const IfStmt *IfStatement,
 713     const Expr *BoolLiteral) {
 714   const Stmt *ElseStatement = IfStatement->getElse();
 715   issueDiag(Context, BoolLiteral->getBeginLoc(), SimplifyConditionDiagnostic,
 716             IfStatement->getSourceRange(),
 717             ElseStatement ? getText(Context, *ElseStatement) : "");
 718 }
 719
 720 void SimplifyBooleanExprCheck::replaceWithCondition(
 721     const ASTContext &Context, const ConditionalOperator *Ternary,
 722     bool Negated) {
 723   std::string Replacement =
 724       replacementExpression(Context, Negated, Ternary->getCond());
 725   issueDiag(Context, Ternary->getTrueExpr()->getBeginLoc(),
 726             "redundant boolean literal in ternary expression result",
 727             Ternary->getSourceRange(), Replacement);
 728 }
 729
 730 void SimplifyBooleanExprCheck::replaceWithReturnCondition(
 731     const ASTContext &Context, const IfStmt *If, const Expr *BoolLiteral,
 732     bool Negated) {
 733   StringRef Terminator = isa<CompoundStmt>(If->getElse()) ? ";" : "";
 734   std::string Condition =
 735       replacementExpression(Context, Negated, If->getCond());
 736   std::string Replacement = ("return " + Condition + Terminator).str();
 737   SourceLocation Start = BoolLiteral->getBeginLoc();
 738   issueDiag(Context, Start, SimplifyConditionalReturnDiagnostic,
 739             If->getSourceRange(), Replacement);
 740 }
 741
 742 void SimplifyBooleanExprCheck::replaceCompoundReturnWithCondition(
 743     const ASTContext &Context, const ReturnStmt *Ret, bool Negated,
 744     const IfStmt *If, const Expr *ThenReturn) {
 745   const std::string Replacement =
 746       "return " + replacementExpression(Context, Negated, If->getCond());
 747   issueDiag(Context, ThenReturn->getBeginLoc(),
 748             SimplifyConditionalReturnDiagnostic,
 749             SourceRange(If->getBeginLoc(), Ret->getEndLoc()), Replacement);
 750 }
 751
 752 void SimplifyBooleanExprCheck::replaceWithAssignment(const ASTContext &Context,
 753                                                      const IfStmt *IfAssign,
 754                                                      const Expr *Var,
 755                                                      SourceLocation Loc,
 756                                                      bool Negated) {
 757   SourceRange Range = IfAssign->getSourceRange();
 758   StringRef VariableName = getText(Context, *Var);
 759   StringRef Terminator = isa<CompoundStmt>(IfAssign->getElse()) ? ";" : "";
 760   std::string Condition =
 761       replacementExpression(Context, Negated, IfAssign->getCond());
 762   std::string Replacement =
 763       (VariableName + " = " + Condition + Terminator).str();
 764   issueDiag(Context, Loc, "redundant boolean literal in conditional assignment",
 765             Range, Replacement);
 766 }
 767
 768 /// Swaps a \c BinaryOperator opcode from `&&` to `||` or vice-versa.
 769 static bool flipDemorganOperator(llvm::SmallVectorImpl<FixItHint> &Output,
 770                                  const BinaryOperator *BO) {
 771   assert(BO->isLogicalOp());
 772   if (BO->getOperatorLoc().isMacroID())
 773     return true;
 774   Output.push_back(FixItHint::CreateReplacement(
 775       BO->getOperatorLoc(), BO->getOpcode() == BO_LAnd ? "||" : "&&"));
 776   return false;
 777 }
 778
 779 static BinaryOperatorKind getDemorganFlippedOperator(BinaryOperatorKind BO) {
 780   assert(BinaryOperator::isLogicalOp(BO));
 781   return BO == BO_LAnd ? BO_LOr : BO_LAnd;
 782 }
 783
 784 static bool flipDemorganSide(SmallVectorImpl<FixItHint> &Fixes,
 785                              const ASTContext &Ctx, const Expr *E,
 786                              std::optional<BinaryOperatorKind> OuterBO);
 787
 788 /// Inverts \p BinOp, Removing \p Parens if they exist and are safe to remove.
 789 /// returns \c true if there is any issue building the Fixes, \c false
 790 /// otherwise.
 791 static bool
 792 flipDemorganBinaryOperator(SmallVectorImpl<FixItHint> &Fixes,
 793                            const ASTContext &Ctx, const BinaryOperator *BinOp,
 794                            std::optional<BinaryOperatorKind> OuterBO,
 795                            const ParenExpr *Parens = nullptr) {
 796   switch (BinOp->getOpcode()) {
 797   case BO_LAnd:
 798   case BO_LOr: {
 799     // if we have 'a && b' or 'a || b', use demorgan to flip it to '!a || !b'
 800     // or '!a && !b'.
 801     if (flipDemorganOperator(Fixes, BinOp))
 802       return true;
 803     auto NewOp = getDemorganFlippedOperator(BinOp->getOpcode());
 804     if (OuterBO) {
 805       // The inner parens are technically needed in a fix for
 806       // `!(!A1 && !(A2 || A3)) -> (A1 || (A2 && A3))`,
 807       // however this would trip the LogicalOpParentheses warning.
 808       // FIXME: Make this user configurable or detect if that warning is
 809       // enabled.
 810       constexpr bool LogicalOpParentheses = true;
 811       if (((*OuterBO == NewOp) || (!LogicalOpParentheses &&
 812                                    (*OuterBO == BO_LOr && NewOp == BO_LAnd))) &&
 813           Parens) {
 814         if (!Parens->getLParen().isMacroID() &&
 815             !Parens->getRParen().isMacroID()) {
 816           Fixes.push_back(FixItHint::CreateRemoval(Parens->getLParen()));
 817           Fixes.push_back(FixItHint::CreateRemoval(Parens->getRParen()));
 818         }
 819       }
 820       if (*OuterBO == BO_LAnd && NewOp == BO_LOr && !Parens) {
 821         Fixes.push_back(FixItHint::CreateInsertion(BinOp->getBeginLoc(), "("));
 822         Fixes.push_back(FixItHint::CreateInsertion(
 823             Lexer::getLocForEndOfToken(BinOp->getEndLoc(), 0,
 824                                        Ctx.getSourceManager(),
 825                                        Ctx.getLangOpts()),
 826             ")"));
 827       }
 828     }
 829     if (flipDemorganSide(Fixes, Ctx, BinOp->getLHS(), NewOp) ||
 830         flipDemorganSide(Fixes, Ctx, BinOp->getRHS(), NewOp))
 831       return true;
 832     return false;
 833   };
 834   case BO_LT:
 835   case BO_GT:
 836   case BO_LE:
 837   case BO_GE:
 838   case BO_EQ:
 839   case BO_NE:
 840     // For comparison operators, just negate the comparison.
 841     if (BinOp->getOperatorLoc().isMacroID())
 842       return true;
 843     Fixes.push_back(FixItHint::CreateReplacement(
 844         BinOp->getOperatorLoc(),
 845         BinaryOperator::getOpcodeStr(
 846             BinaryOperator::negateComparisonOp(BinOp->getOpcode()))));
 847     return false;
 848   default:
 849     // for any other binary operator, just use logical not and wrap in
 850     // parens.
 851     if (Parens) {
 852       if (Parens->getBeginLoc().isMacroID())
 853         return true;
 854       Fixes.push_back(FixItHint::CreateInsertion(Parens->getBeginLoc(), "!"));
 855     } else {
 856       if (BinOp->getBeginLoc().isMacroID() || BinOp->getEndLoc().isMacroID())
 857         return true;
 858       Fixes.append({FixItHint::CreateInsertion(BinOp->getBeginLoc(), "!("),
 859                     FixItHint::CreateInsertion(
 860                         Lexer::getLocForEndOfToken(BinOp->getEndLoc(), 0,
 861                                                    Ctx.getSourceManager(),
 862                                                    Ctx.getLangOpts()),
 863                         ")")});
 864     }
 865     break;
 866   }
 867   return false;
 868 }
 869
 870 static bool flipDemorganSide(SmallVectorImpl<FixItHint> &Fixes,
 871                              const ASTContext &Ctx, const Expr *E,
 872                              std::optional<BinaryOperatorKind> OuterBO) {
 873   if (isa<UnaryOperator>(E) && cast<UnaryOperator>(E)->getOpcode() == UO_LNot) {
 874     //  if we have a not operator, '!a', just remove the '!'.
 875     if (cast<UnaryOperator>(E)->getOperatorLoc().isMacroID())
 876       return true;
 877     Fixes.push_back(
 878         FixItHint::CreateRemoval(cast<UnaryOperator>(E)->getOperatorLoc()));
 879     return false;
 880   }
 881   if (const auto *BinOp = dyn_cast<BinaryOperator>(E)) {
 882     return flipDemorganBinaryOperator(Fixes, Ctx, BinOp, OuterBO);
 883   }
 884   if (const auto *Paren = dyn_cast<ParenExpr>(E)) {
 885     if (const auto *BinOp = dyn_cast<BinaryOperator>(Paren->getSubExpr())) {
 886       return flipDemorganBinaryOperator(Fixes, Ctx, BinOp, OuterBO, Paren);
 887     }
 888   }
 889   // Fallback case just insert a logical not operator.
 890   if (E->getBeginLoc().isMacroID())
 891     return true;
 892   Fixes.push_back(FixItHint::CreateInsertion(E->getBeginLoc(), "!"));
 893   return false;
 894 }
 895
 896 static bool shouldRemoveParens(const Stmt *Parent,
 897                                BinaryOperatorKind NewOuterBinary,
 898                                const ParenExpr *Parens) {
 899   if (!Parens)
 900     return false;
 901   if (!Parent)
 902     return true;
 903   switch (Parent->getStmtClass()) {
 904   case Stmt::BinaryOperatorClass: {
 905     const auto *BO = cast<BinaryOperator>(Parent);
 906     if (BO->isAssignmentOp())
 907       return true;
 908     if (BO->isCommaOp())
 909       return true;
 910     if (BO->getOpcode() == NewOuterBinary)
 911       return true;
 912     return false;
 913   }
 914   case Stmt::UnaryOperatorClass:
 915   case Stmt::CXXRewrittenBinaryOperatorClass:
 916     return false;
 917   default:
 918     return true;
 919   }
 920 }
 921
 922 bool SimplifyBooleanExprCheck::reportDeMorgan(const ASTContext &Context,
 923                                               const UnaryOperator *Outer,
 924                                               const BinaryOperator *Inner,
 925                                               bool TryOfferFix,
 926                                               const Stmt *Parent,
 927                                               const ParenExpr *Parens) {
 928   assert(Outer);
 929   assert(Inner);
 930   assert(Inner->isLogicalOp());
 931
 932   auto Diag =
 933       diag(Outer->getBeginLoc(),
 934            "boolean expression can be simplified by DeMorgan's theorem");
 935   Diag << Outer->getSourceRange();
 936   // If we have already fixed this with a previous fix, don't attempt any fixes
 937   if (!TryOfferFix)
 938     return false;
 939   if (Outer->getOperatorLoc().isMacroID())
 940     return false;
 941   SmallVector<FixItHint> Fixes;
 942   auto NewOpcode = getDemorganFlippedOperator(Inner->getOpcode());
 943   if (shouldRemoveParens(Parent, NewOpcode, Parens)) {
 944     Fixes.push_back(FixItHint::CreateRemoval(
 945         SourceRange(Outer->getOperatorLoc(), Parens->getLParen())));
 946     Fixes.push_back(FixItHint::CreateRemoval(Parens->getRParen()));
 947   } else {
 948     Fixes.push_back(FixItHint::CreateRemoval(Outer->getOperatorLoc()));
 949   }
 950   if (flipDemorganOperator(Fixes, Inner))
 951     return false;
 952   if (flipDemorganSide(Fixes, Context, Inner->getLHS(), NewOpcode) ||
 953       flipDemorganSide(Fixes, Context, Inner->getRHS(), NewOpcode))
 954     return false;
 955   Diag << Fixes;
 956   return true;
 957 }
 958 } // namespace clang::tidy::readability