clang-tools-extra/clang-tidy/misc/RedundantExpressionCheck.cpp

   1 //===--- RedundantExpressionCheck.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 "RedundantExpressionCheck.h"
  10 #include "../utils/Matchers.h"
  11 #include "../utils/OptionsUtils.h"
  12 #include "clang/AST/ASTContext.h"
  13 #include "clang/AST/ExprConcepts.h"
  14 #include "clang/ASTMatchers/ASTMatchFinder.h"
  15 #include "clang/Basic/LLVM.h"
  16 #include "clang/Basic/SourceLocation.h"
  17 #include "clang/Basic/SourceManager.h"
  18 #include "clang/Lex/Lexer.h"
  19 #include "llvm/ADT/APInt.h"
  20 #include "llvm/ADT/APSInt.h"
  21 #include "llvm/ADT/FoldingSet.h"
  22 #include "llvm/ADT/SmallBitVector.h"
  23 #include "llvm/Support/Casting.h"
  24 #include "llvm/Support/FormatVariadic.h"
  25 #include <algorithm>
  26 #include <cassert>
  27 #include <cstdint>
  28 #include <optional>
  29 #include <string>
  30 #include <vector>
  31
  32 using namespace clang::ast_matchers;
  33 using namespace clang::tidy::matchers;
  34
  35 namespace clang::tidy::misc {
  36 namespace {
  37 using llvm::APSInt;
  38
  39 static constexpr llvm::StringLiteral KnownBannedMacroNames[] = {
  40     "EAGAIN",
  41     "EWOULDBLOCK",
  42     "SIGCLD",
  43     "SIGCHLD",
  44 };
  45
  46 static bool incrementWithoutOverflow(const APSInt &Value, APSInt &Result) {
  47   Result = Value;
  48   ++Result;
  49   return Value < Result;
  50 }
  51
  52 static bool areEquivalentNameSpecifier(const NestedNameSpecifier *Left,
  53                                        const NestedNameSpecifier *Right) {
  54   llvm::FoldingSetNodeID LeftID, RightID;
  55   Left->Profile(LeftID);
  56   Right->Profile(RightID);
  57   return LeftID == RightID;
  58 }
  59
  60 static bool areEquivalentExpr(const Expr *Left, const Expr *Right) {
  61   if (!Left || !Right)
  62     return !Left && !Right;
  63
  64   Left = Left->IgnoreParens();
  65   Right = Right->IgnoreParens();
  66
  67   // Compare classes.
  68   if (Left->getStmtClass() != Right->getStmtClass())
  69     return false;
  70
  71   // Compare children.
  72   Expr::const_child_iterator LeftIter = Left->child_begin();
  73   Expr::const_child_iterator RightIter = Right->child_begin();
  74   while (LeftIter != Left->child_end() && RightIter != Right->child_end()) {
  75     if (!areEquivalentExpr(dyn_cast_or_null<Expr>(*LeftIter),
  76                            dyn_cast_or_null<Expr>(*RightIter)))
  77       return false;
  78     ++LeftIter;
  79     ++RightIter;
  80   }
  81   if (LeftIter != Left->child_end() || RightIter != Right->child_end())
  82     return false;
  83
  84   // Perform extra checks.
  85   switch (Left->getStmtClass()) {
  86   default:
  87     return false;
  88
  89   case Stmt::CharacterLiteralClass:
  90     return cast<CharacterLiteral>(Left)->getValue() ==
  91            cast<CharacterLiteral>(Right)->getValue();
  92   case Stmt::IntegerLiteralClass: {
  93     llvm::APInt LeftLit = cast<IntegerLiteral>(Left)->getValue();
  94     llvm::APInt RightLit = cast<IntegerLiteral>(Right)->getValue();
  95     return LeftLit.getBitWidth() == RightLit.getBitWidth() &&
  96            LeftLit == RightLit;
  97   }
  98   case Stmt::FloatingLiteralClass:
  99     return cast<FloatingLiteral>(Left)->getValue().bitwiseIsEqual(
 100         cast<FloatingLiteral>(Right)->getValue());
 101   case Stmt::StringLiteralClass:
 102     return cast<StringLiteral>(Left)->getBytes() ==
 103            cast<StringLiteral>(Right)->getBytes();
 104   case Stmt::CXXOperatorCallExprClass:
 105     return cast<CXXOperatorCallExpr>(Left)->getOperator() ==
 106            cast<CXXOperatorCallExpr>(Right)->getOperator();
 107   case Stmt::DependentScopeDeclRefExprClass:
 108     if (cast<DependentScopeDeclRefExpr>(Left)->getDeclName() !=
 109         cast<DependentScopeDeclRefExpr>(Right)->getDeclName())
 110       return false;
 111     return areEquivalentNameSpecifier(
 112         cast<DependentScopeDeclRefExpr>(Left)->getQualifier(),
 113         cast<DependentScopeDeclRefExpr>(Right)->getQualifier());
 114   case Stmt::DeclRefExprClass:
 115     return cast<DeclRefExpr>(Left)->getDecl() ==
 116            cast<DeclRefExpr>(Right)->getDecl();
 117   case Stmt::MemberExprClass:
 118     return cast<MemberExpr>(Left)->getMemberDecl() ==
 119            cast<MemberExpr>(Right)->getMemberDecl();
 120   case Stmt::CXXFoldExprClass:
 121     return cast<CXXFoldExpr>(Left)->getOperator() ==
 122            cast<CXXFoldExpr>(Right)->getOperator();
 123   case Stmt::CXXFunctionalCastExprClass:
 124   case Stmt::CStyleCastExprClass:
 125     return cast<ExplicitCastExpr>(Left)->getTypeAsWritten() ==
 126            cast<ExplicitCastExpr>(Right)->getTypeAsWritten();
 127   case Stmt::CallExprClass:
 128   case Stmt::ImplicitCastExprClass:
 129   case Stmt::ArraySubscriptExprClass:
 130     return true;
 131   case Stmt::UnaryOperatorClass:
 132     if (cast<UnaryOperator>(Left)->isIncrementDecrementOp())
 133       return false;
 134     return cast<UnaryOperator>(Left)->getOpcode() ==
 135            cast<UnaryOperator>(Right)->getOpcode();
 136   case Stmt::BinaryOperatorClass:
 137     if (cast<BinaryOperator>(Left)->isAssignmentOp())
 138       return false;
 139     return cast<BinaryOperator>(Left)->getOpcode() ==
 140            cast<BinaryOperator>(Right)->getOpcode();
 141   case Stmt::UnaryExprOrTypeTraitExprClass:
 142     const auto *LeftUnaryExpr =
 143         cast<UnaryExprOrTypeTraitExpr>(Left);
 144     const auto *RightUnaryExpr =
 145         cast<UnaryExprOrTypeTraitExpr>(Right);
 146     if (LeftUnaryExpr->isArgumentType() && RightUnaryExpr->isArgumentType())
 147       return LeftUnaryExpr->getKind() == RightUnaryExpr->getKind() &&
 148              LeftUnaryExpr->getArgumentType() ==
 149                  RightUnaryExpr->getArgumentType();
 150     if (!LeftUnaryExpr->isArgumentType() && !RightUnaryExpr->isArgumentType())
 151       return areEquivalentExpr(LeftUnaryExpr->getArgumentExpr(),
 152                                RightUnaryExpr->getArgumentExpr());
 153
 154     return false;
 155   }
 156 }
 157
 158 // For a given expression 'x', returns whether the ranges covered by the
 159 // relational operators are equivalent (i.e.  x <= 4 is equivalent to x < 5).
 160 static bool areEquivalentRanges(BinaryOperatorKind OpcodeLHS,
 161                                 const APSInt &ValueLHS,
 162                                 BinaryOperatorKind OpcodeRHS,
 163                                 const APSInt &ValueRHS) {
 164   assert(APSInt::compareValues(ValueLHS, ValueRHS) <= 0 &&
 165          "Values must be ordered");
 166   // Handle the case where constants are the same: x <= 4  <==>  x <= 4.
 167   if (APSInt::compareValues(ValueLHS, ValueRHS) == 0)
 168     return OpcodeLHS == OpcodeRHS;
 169
 170   // Handle the case where constants are off by one: x <= 4  <==>  x < 5.
 171   APSInt ValueLhsPlus1;
 172   return ((OpcodeLHS == BO_LE && OpcodeRHS == BO_LT) ||
 173           (OpcodeLHS == BO_GT && OpcodeRHS == BO_GE)) &&
 174          incrementWithoutOverflow(ValueLHS, ValueLhsPlus1) &&
 175          APSInt::compareValues(ValueLhsPlus1, ValueRHS) == 0;
 176 }
 177
 178 // For a given expression 'x', returns whether the ranges covered by the
 179 // relational operators are fully disjoint (i.e. x < 4  and  x > 7).
 180 static bool areExclusiveRanges(BinaryOperatorKind OpcodeLHS,
 181                                const APSInt &ValueLHS,
 182                                BinaryOperatorKind OpcodeRHS,
 183                                const APSInt &ValueRHS) {
 184   assert(APSInt::compareValues(ValueLHS, ValueRHS) <= 0 &&
 185          "Values must be ordered");
 186
 187   // Handle cases where the constants are the same.
 188   if (APSInt::compareValues(ValueLHS, ValueRHS) == 0) {
 189     switch (OpcodeLHS) {
 190     case BO_EQ:
 191       return OpcodeRHS == BO_NE || OpcodeRHS == BO_GT || OpcodeRHS == BO_LT;
 192     case BO_NE:
 193       return OpcodeRHS == BO_EQ;
 194     case BO_LE:
 195       return OpcodeRHS == BO_GT;
 196     case BO_GE:
 197       return OpcodeRHS == BO_LT;
 198     case BO_LT:
 199       return OpcodeRHS == BO_EQ || OpcodeRHS == BO_GT || OpcodeRHS == BO_GE;
 200     case BO_GT:
 201       return OpcodeRHS == BO_EQ || OpcodeRHS == BO_LT || OpcodeRHS == BO_LE;
 202     default:
 203       return false;
 204     }
 205   }
 206
 207   // Handle cases where the constants are different.
 208   if ((OpcodeLHS == BO_EQ || OpcodeLHS == BO_LT || OpcodeLHS == BO_LE) &&
 209       (OpcodeRHS == BO_EQ || OpcodeRHS == BO_GT || OpcodeRHS == BO_GE))
 210     return true;
 211
 212   // Handle the case where constants are off by one: x > 5 && x < 6.
 213   APSInt ValueLhsPlus1;
 214   if (OpcodeLHS == BO_GT && OpcodeRHS == BO_LT &&
 215       incrementWithoutOverflow(ValueLHS, ValueLhsPlus1) &&
 216       APSInt::compareValues(ValueLhsPlus1, ValueRHS) == 0)
 217     return true;
 218
 219   return false;
 220 }
 221
 222 // Returns whether the ranges covered by the union of both relational
 223 // expressions cover the whole domain (i.e. x < 10  and  x > 0).
 224 static bool rangesFullyCoverDomain(BinaryOperatorKind OpcodeLHS,
 225                                    const APSInt &ValueLHS,
 226                                    BinaryOperatorKind OpcodeRHS,
 227                                    const APSInt &ValueRHS) {
 228   assert(APSInt::compareValues(ValueLHS, ValueRHS) <= 0 &&
 229          "Values must be ordered");
 230
 231   // Handle cases where the constants are the same:  x < 5 || x >= 5.
 232   if (APSInt::compareValues(ValueLHS, ValueRHS) == 0) {
 233     switch (OpcodeLHS) {
 234     case BO_EQ:
 235       return OpcodeRHS == BO_NE;
 236     case BO_NE:
 237       return OpcodeRHS == BO_EQ;
 238     case BO_LE:
 239       return OpcodeRHS == BO_GT || OpcodeRHS == BO_GE;
 240     case BO_LT:
 241       return OpcodeRHS == BO_GE;
 242     case BO_GE:
 243       return OpcodeRHS == BO_LT || OpcodeRHS == BO_LE;
 244     case BO_GT:
 245       return OpcodeRHS == BO_LE;
 246     default:
 247       return false;
 248     }
 249   }
 250
 251   // Handle the case where constants are off by one: x <= 4 || x >= 5.
 252   APSInt ValueLhsPlus1;
 253   if (OpcodeLHS == BO_LE && OpcodeRHS == BO_GE &&
 254       incrementWithoutOverflow(ValueLHS, ValueLhsPlus1) &&
 255       APSInt::compareValues(ValueLhsPlus1, ValueRHS) == 0)
 256     return true;
 257
 258   // Handle cases where the constants are different: x > 4 || x <= 7.
 259   if ((OpcodeLHS == BO_GT || OpcodeLHS == BO_GE) &&
 260       (OpcodeRHS == BO_LT || OpcodeRHS == BO_LE))
 261     return true;
 262
 263   // Handle cases where constants are different but both ops are !=, like:
 264   // x != 5 || x != 10
 265   if (OpcodeLHS == BO_NE && OpcodeRHS == BO_NE)
 266     return true;
 267
 268   return false;
 269 }
 270
 271 static bool rangeSubsumesRange(BinaryOperatorKind OpcodeLHS,
 272                                const APSInt &ValueLHS,
 273                                BinaryOperatorKind OpcodeRHS,
 274                                const APSInt &ValueRHS) {
 275   int Comparison = APSInt::compareValues(ValueLHS, ValueRHS);
 276   switch (OpcodeLHS) {
 277   case BO_EQ:
 278     return OpcodeRHS == BO_EQ && Comparison == 0;
 279   case BO_NE:
 280     return (OpcodeRHS == BO_NE && Comparison == 0) ||
 281            (OpcodeRHS == BO_EQ && Comparison != 0) ||
 282            (OpcodeRHS == BO_LT && Comparison >= 0) ||
 283            (OpcodeRHS == BO_LE && Comparison > 0) ||
 284            (OpcodeRHS == BO_GT && Comparison <= 0) ||
 285            (OpcodeRHS == BO_GE && Comparison < 0);
 286
 287   case BO_LT:
 288     return ((OpcodeRHS == BO_LT && Comparison >= 0) ||
 289             (OpcodeRHS == BO_LE && Comparison > 0) ||
 290             (OpcodeRHS == BO_EQ && Comparison > 0));
 291   case BO_GT:
 292     return ((OpcodeRHS == BO_GT && Comparison <= 0) ||
 293             (OpcodeRHS == BO_GE && Comparison < 0) ||
 294             (OpcodeRHS == BO_EQ && Comparison < 0));
 295   case BO_LE:
 296     return (OpcodeRHS == BO_LT || OpcodeRHS == BO_LE || OpcodeRHS == BO_EQ) &&
 297            Comparison >= 0;
 298   case BO_GE:
 299     return (OpcodeRHS == BO_GT || OpcodeRHS == BO_GE || OpcodeRHS == BO_EQ) &&
 300            Comparison <= 0;
 301   default:
 302     return false;
 303   }
 304 }
 305
 306 static void transformSubToCanonicalAddExpr(BinaryOperatorKind &Opcode,
 307                                            APSInt &Value) {
 308   if (Opcode == BO_Sub) {
 309     Opcode = BO_Add;
 310     Value = -Value;
 311   }
 312 }
 313
 314 // to use in the template below
 315 static OverloadedOperatorKind getOp(const BinaryOperator *Op) {
 316   return BinaryOperator::getOverloadedOperator(Op->getOpcode());
 317 }
 318
 319 static OverloadedOperatorKind getOp(const CXXOperatorCallExpr *Op) {
 320   if (Op->getNumArgs() != 2)
 321     return OO_None;
 322   return Op->getOperator();
 323 }
 324
 325 static std::pair<const Expr *, const Expr *>
 326 getOperands(const BinaryOperator *Op) {
 327   return {Op->getLHS()->IgnoreParenImpCasts(),
 328           Op->getRHS()->IgnoreParenImpCasts()};
 329 }
 330
 331 static std::pair<const Expr *, const Expr *>
 332 getOperands(const CXXOperatorCallExpr *Op) {
 333   return {Op->getArg(0)->IgnoreParenImpCasts(),
 334           Op->getArg(1)->IgnoreParenImpCasts()};
 335 }
 336
 337 template <typename TExpr>
 338 static const TExpr *checkOpKind(const Expr *TheExpr,
 339                                 OverloadedOperatorKind OpKind) {
 340   const auto *AsTExpr = dyn_cast_or_null<TExpr>(TheExpr);
 341   if (AsTExpr && getOp(AsTExpr) == OpKind)
 342     return AsTExpr;
 343
 344   return nullptr;
 345 }
 346
 347 // returns true if a subexpression has two directly equivalent operands and
 348 // is already handled by operands/parametersAreEquivalent
 349 template <typename TExpr, unsigned N>
 350 static bool collectOperands(const Expr *Part,
 351                             SmallVector<const Expr *, N> &AllOperands,
 352                             OverloadedOperatorKind OpKind) {
 353   if (const auto *BinOp = checkOpKind<TExpr>(Part, OpKind)) {
 354     const std::pair<const Expr *, const Expr *> Operands = getOperands(BinOp);
 355     if (areEquivalentExpr(Operands.first, Operands.second))
 356       return true;
 357     return collectOperands<TExpr>(Operands.first, AllOperands, OpKind) ||
 358            collectOperands<TExpr>(Operands.second, AllOperands, OpKind);
 359   }
 360
 361   AllOperands.push_back(Part);
 362   return false;
 363 }
 364
 365 template <typename TExpr>
 366 static bool hasSameOperatorParent(const Expr *TheExpr,
 367                                   OverloadedOperatorKind OpKind,
 368                                   ASTContext &Context) {
 369   // IgnoreParenImpCasts logic in reverse: skip surrounding uninteresting nodes
 370   const DynTypedNodeList Parents = Context.getParents(*TheExpr);
 371   for (DynTypedNode DynParent : Parents) {
 372     if (const auto *Parent = DynParent.get<Expr>()) {
 373       bool Skip = isa<ParenExpr>(Parent) || isa<ImplicitCastExpr>(Parent) ||
 374                   isa<FullExpr>(Parent) ||
 375                   isa<MaterializeTemporaryExpr>(Parent);
 376       if (Skip && hasSameOperatorParent<TExpr>(Parent, OpKind, Context))
 377         return true;
 378       if (checkOpKind<TExpr>(Parent, OpKind))
 379         return true;
 380     }
 381   }
 382
 383   return false;
 384 }
 385
 386 template <typename TExpr>
 387 static bool
 388 markDuplicateOperands(const TExpr *TheExpr,
 389                       ast_matchers::internal::BoundNodesTreeBuilder *Builder,
 390                       ASTContext &Context) {
 391   const OverloadedOperatorKind OpKind = getOp(TheExpr);
 392   if (OpKind == OO_None)
 393     return false;
 394   // if there are no nested operators of the same kind, it's handled by
 395   // operands/parametersAreEquivalent
 396   const std::pair<const Expr *, const Expr *> Operands = getOperands(TheExpr);
 397   if (!(checkOpKind<TExpr>(Operands.first, OpKind) ||
 398         checkOpKind<TExpr>(Operands.second, OpKind)))
 399     return false;
 400
 401   // if parent is the same kind of operator, it's handled by a previous call to
 402   // markDuplicateOperands
 403   if (hasSameOperatorParent<TExpr>(TheExpr, OpKind, Context))
 404     return false;
 405
 406   SmallVector<const Expr *, 4> AllOperands;
 407   if (collectOperands<TExpr>(Operands.first, AllOperands, OpKind))
 408     return false;
 409   if (collectOperands<TExpr>(Operands.second, AllOperands, OpKind))
 410     return false;
 411   size_t NumOperands = AllOperands.size();
 412   llvm::SmallBitVector Duplicates(NumOperands);
 413   for (size_t I = 0; I < NumOperands; I++) {
 414     if (Duplicates[I])
 415       continue;
 416     bool FoundDuplicates = false;
 417
 418     for (size_t J = I + 1; J < NumOperands; J++) {
 419       if (AllOperands[J]->HasSideEffects(Context))
 420         break;
 421
 422       if (areEquivalentExpr(AllOperands[I], AllOperands[J])) {
 423         FoundDuplicates = true;
 424         Duplicates.set(J);
 425         Builder->setBinding(SmallString<11>(llvm::formatv("duplicate{0}", J)),
 426                             DynTypedNode::create(*AllOperands[J]));
 427       }
 428     }
 429
 430     if (FoundDuplicates)
 431       Builder->setBinding(SmallString<11>(llvm::formatv("duplicate{0}", I)),
 432                           DynTypedNode::create(*AllOperands[I]));
 433   }
 434
 435   return Duplicates.any();
 436 }
 437
 438 AST_MATCHER(Expr, isIntegerConstantExpr) {
 439   if (Node.isInstantiationDependent())
 440     return false;
 441   return Node.isIntegerConstantExpr(Finder->getASTContext());
 442 }
 443
 444 AST_MATCHER(Expr, isRequiresExpr) { return isa<RequiresExpr>(Node); }
 445
 446 AST_MATCHER(BinaryOperator, operandsAreEquivalent) {
 447   return areEquivalentExpr(Node.getLHS(), Node.getRHS());
 448 }
 449
 450 AST_MATCHER(BinaryOperator, nestedOperandsAreEquivalent) {
 451   return markDuplicateOperands(&Node, Builder, Finder->getASTContext());
 452 }
 453
 454 AST_MATCHER(ConditionalOperator, expressionsAreEquivalent) {
 455   return areEquivalentExpr(Node.getTrueExpr(), Node.getFalseExpr());
 456 }
 457
 458 AST_MATCHER(CallExpr, parametersAreEquivalent) {
 459   return Node.getNumArgs() == 2 &&
 460          areEquivalentExpr(Node.getArg(0), Node.getArg(1));
 461 }
 462
 463 AST_MATCHER(CXXOperatorCallExpr, nestedParametersAreEquivalent) {
 464   return markDuplicateOperands(&Node, Builder, Finder->getASTContext());
 465 }
 466
 467 AST_MATCHER(BinaryOperator, binaryOperatorIsInMacro) {
 468   return Node.getOperatorLoc().isMacroID();
 469 }
 470
 471 AST_MATCHER(ConditionalOperator, conditionalOperatorIsInMacro) {
 472   return Node.getQuestionLoc().isMacroID() || Node.getColonLoc().isMacroID();
 473 }
 474
 475 AST_MATCHER(Expr, isMacro) { return Node.getExprLoc().isMacroID(); }
 476
 477 AST_MATCHER_P(Expr, expandedByMacro, ArrayRef<llvm::StringLiteral>, Names) {
 478   const SourceManager &SM = Finder->getASTContext().getSourceManager();
 479   const LangOptions &LO = Finder->getASTContext().getLangOpts();
 480   SourceLocation Loc = Node.getExprLoc();
 481   while (Loc.isMacroID()) {
 482     StringRef MacroName = Lexer::getImmediateMacroName(Loc, SM, LO);
 483     if (llvm::is_contained(Names, MacroName))
 484       return true;
 485     Loc = SM.getImmediateMacroCallerLoc(Loc);
 486   }
 487   return false;
 488 }
 489
 490 // Returns a matcher for integer constant expressions.
 491 static ast_matchers::internal::Matcher<Expr>
 492 matchIntegerConstantExpr(StringRef Id) {
 493   std::string CstId = (Id + "-const").str();
 494   return expr(isIntegerConstantExpr()).bind(CstId);
 495 }
 496
 497 // Retrieves the integer expression matched by 'matchIntegerConstantExpr' with
 498 // name 'Id' and stores it into 'ConstExpr', the value of the expression is
 499 // stored into `Value`.
 500 static bool retrieveIntegerConstantExpr(const MatchFinder::MatchResult &Result,
 501                                         StringRef Id, APSInt &Value,
 502                                         const Expr *&ConstExpr) {
 503   std::string CstId = (Id + "-const").str();
 504   ConstExpr = Result.Nodes.getNodeAs<Expr>(CstId);
 505   if (!ConstExpr)
 506     return false;
 507   std::optional<llvm::APSInt> R =
 508       ConstExpr->getIntegerConstantExpr(*Result.Context);
 509   if (!R)
 510     return false;
 511   Value = *R;
 512   return true;
 513 }
 514
 515 // Overloaded `retrieveIntegerConstantExpr` for compatibility.
 516 static bool retrieveIntegerConstantExpr(const MatchFinder::MatchResult &Result,
 517                                         StringRef Id, APSInt &Value) {
 518   const Expr *ConstExpr = nullptr;
 519   return retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr);
 520 }
 521
 522 // Returns a matcher for symbolic expressions (matches every expression except
 523 // ingeter constant expressions).
 524 static ast_matchers::internal::Matcher<Expr> matchSymbolicExpr(StringRef Id) {
 525   std::string SymId = (Id + "-sym").str();
 526   return ignoringParenImpCasts(
 527       expr(unless(isIntegerConstantExpr())).bind(SymId));
 528 }
 529
 530 // Retrieves the expression matched by 'matchSymbolicExpr' with name 'Id' and
 531 // stores it into 'SymExpr'.
 532 static bool retrieveSymbolicExpr(const MatchFinder::MatchResult &Result,
 533                                  StringRef Id, const Expr *&SymExpr) {
 534   std::string SymId = (Id + "-sym").str();
 535   if (const auto *Node = Result.Nodes.getNodeAs<Expr>(SymId)) {
 536     SymExpr = Node;
 537     return true;
 538   }
 539   return false;
 540 }
 541
 542 // Match a binary operator between a symbolic expression and an integer constant
 543 // expression.
 544 static ast_matchers::internal::Matcher<Expr>
 545 matchBinOpIntegerConstantExpr(StringRef Id) {
 546   const auto BinOpCstExpr =
 547       expr(anyOf(binaryOperator(hasAnyOperatorName("+", "|", "&"),
 548                                 hasOperands(matchSymbolicExpr(Id),
 549                                             matchIntegerConstantExpr(Id))),
 550                  binaryOperator(hasOperatorName("-"),
 551                                 hasLHS(matchSymbolicExpr(Id)),
 552                                 hasRHS(matchIntegerConstantExpr(Id)))))
 553           .bind(Id);
 554   return ignoringParenImpCasts(BinOpCstExpr);
 555 }
 556
 557 // Retrieves sub-expressions matched by 'matchBinOpIntegerConstantExpr' with
 558 // name 'Id'.
 559 static bool
 560 retrieveBinOpIntegerConstantExpr(const MatchFinder::MatchResult &Result,
 561                                  StringRef Id, BinaryOperatorKind &Opcode,
 562                                  const Expr *&Symbol, APSInt &Value) {
 563   if (const auto *BinExpr = Result.Nodes.getNodeAs<BinaryOperator>(Id)) {
 564     Opcode = BinExpr->getOpcode();
 565     return retrieveSymbolicExpr(Result, Id, Symbol) &&
 566            retrieveIntegerConstantExpr(Result, Id, Value);
 567   }
 568   return false;
 569 }
 570
 571 // Matches relational expressions: 'Expr <op> k' (i.e. x < 2, x != 3, 12 <= x).
 572 static ast_matchers::internal::Matcher<Expr>
 573 matchRelationalIntegerConstantExpr(StringRef Id) {
 574   std::string CastId = (Id + "-cast").str();
 575   std::string SwapId = (Id + "-swap").str();
 576   std::string NegateId = (Id + "-negate").str();
 577   std::string OverloadId = (Id + "-overload").str();
 578   std::string ConstId = (Id + "-const").str();
 579
 580   const auto RelationalExpr = ignoringParenImpCasts(binaryOperator(
 581       isComparisonOperator(), expr().bind(Id),
 582       anyOf(allOf(hasLHS(matchSymbolicExpr(Id)),
 583                   hasRHS(matchIntegerConstantExpr(Id))),
 584             allOf(hasLHS(matchIntegerConstantExpr(Id)),
 585                   hasRHS(matchSymbolicExpr(Id)), expr().bind(SwapId)))));
 586
 587   // A cast can be matched as a comparator to zero. (i.e. if (x) is equivalent
 588   // to if (x != 0)).
 589   const auto CastExpr =
 590       implicitCastExpr(hasCastKind(CK_IntegralToBoolean),
 591                        hasSourceExpression(matchSymbolicExpr(Id)))
 592           .bind(CastId);
 593
 594   const auto NegateRelationalExpr =
 595       unaryOperator(hasOperatorName("!"),
 596                     hasUnaryOperand(anyOf(CastExpr, RelationalExpr)))
 597           .bind(NegateId);
 598
 599   // Do not bind to double negation.
 600   const auto NegateNegateRelationalExpr =
 601       unaryOperator(hasOperatorName("!"),
 602                     hasUnaryOperand(unaryOperator(
 603                         hasOperatorName("!"),
 604                         hasUnaryOperand(anyOf(CastExpr, RelationalExpr)))));
 605
 606   const auto OverloadedOperatorExpr =
 607       cxxOperatorCallExpr(
 608           hasAnyOverloadedOperatorName("==", "!=", "<", "<=", ">", ">="),
 609           // Filter noisy false positives.
 610           unless(isMacro()), unless(isInTemplateInstantiation()),
 611           anyOf(hasLHS(ignoringParenImpCasts(integerLiteral().bind(ConstId))),
 612                 hasRHS(ignoringParenImpCasts(integerLiteral().bind(ConstId)))))
 613           .bind(OverloadId);
 614
 615   return anyOf(RelationalExpr, CastExpr, NegateRelationalExpr,
 616                NegateNegateRelationalExpr, OverloadedOperatorExpr);
 617 }
 618
 619 // Checks whether a function param is non constant reference type, and may
 620 // be modified in the function.
 621 static bool isNonConstReferenceType(QualType ParamType) {
 622   return ParamType->isReferenceType() &&
 623          !ParamType.getNonReferenceType().isConstQualified();
 624 }
 625
 626 // Checks whether the arguments of an overloaded operator can be modified in the
 627 // function.
 628 // For operators that take an instance and a constant as arguments, only the
 629 // first argument (the instance) needs to be checked, since the constant itself
 630 // is a temporary expression. Whether the second parameter is checked is
 631 // controlled by the parameter `ParamsToCheckCount`.
 632 static bool
 633 canOverloadedOperatorArgsBeModified(const CXXOperatorCallExpr *OperatorCall,
 634                                     bool CheckSecondParam) {
 635   const auto *OperatorDecl =
 636       dyn_cast_or_null<FunctionDecl>(OperatorCall->getCalleeDecl());
 637   // if we can't find the declaration, conservatively assume it can modify
 638   // arguments
 639   if (!OperatorDecl)
 640     return true;
 641
 642   unsigned ParamCount = OperatorDecl->getNumParams();
 643
 644   // Overloaded operators declared inside a class have only one param.
 645   // These functions must be declared const in order to not be able to modify
 646   // the instance of the class they are called through.
 647   if (ParamCount == 1 &&
 648       !OperatorDecl->getType()->castAs<FunctionType>()->isConst())
 649     return true;
 650
 651   if (isNonConstReferenceType(OperatorDecl->getParamDecl(0)->getType()))
 652     return true;
 653
 654   return CheckSecondParam && ParamCount == 2 &&
 655          isNonConstReferenceType(OperatorDecl->getParamDecl(1)->getType());
 656 }
 657
 658 // Retrieves sub-expressions matched by 'matchRelationalIntegerConstantExpr'
 659 // with name 'Id'.
 660 static bool retrieveRelationalIntegerConstantExpr(
 661     const MatchFinder::MatchResult &Result, StringRef Id,
 662     const Expr *&OperandExpr, BinaryOperatorKind &Opcode, const Expr *&Symbol,
 663     APSInt &Value, const Expr *&ConstExpr) {
 664   std::string CastId = (Id + "-cast").str();
 665   std::string SwapId = (Id + "-swap").str();
 666   std::string NegateId = (Id + "-negate").str();
 667   std::string OverloadId = (Id + "-overload").str();
 668
 669   if (const auto *Bin = Result.Nodes.getNodeAs<BinaryOperator>(Id)) {
 670     // Operand received with explicit comparator.
 671     Opcode = Bin->getOpcode();
 672     OperandExpr = Bin;
 673
 674     if (!retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr))
 675       return false;
 676   } else if (const auto *Cast = Result.Nodes.getNodeAs<CastExpr>(CastId)) {
 677     // Operand received with implicit comparator (cast).
 678     Opcode = BO_NE;
 679     OperandExpr = Cast;
 680     Value = APSInt(32, false);
 681   } else if (const auto *OverloadedOperatorExpr =
 682                  Result.Nodes.getNodeAs<CXXOperatorCallExpr>(OverloadId)) {
 683     if (canOverloadedOperatorArgsBeModified(OverloadedOperatorExpr, false))
 684       return false;
 685
 686     bool IntegerConstantIsFirstArg = false;
 687
 688     if (const auto *Arg = OverloadedOperatorExpr->getArg(1)) {
 689       if (!Arg->isValueDependent() &&
 690           !Arg->isIntegerConstantExpr(*Result.Context)) {
 691         IntegerConstantIsFirstArg = true;
 692         if (const auto *Arg = OverloadedOperatorExpr->getArg(0)) {
 693           if (!Arg->isValueDependent() &&
 694               !Arg->isIntegerConstantExpr(*Result.Context))
 695             return false;
 696         } else
 697           return false;
 698       }
 699     } else
 700       return false;
 701
 702     Symbol = OverloadedOperatorExpr->getArg(IntegerConstantIsFirstArg ? 1 : 0);
 703     OperandExpr = OverloadedOperatorExpr;
 704     Opcode = BinaryOperator::getOverloadedOpcode(OverloadedOperatorExpr->getOperator());
 705
 706     if (!retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr))
 707       return false;
 708
 709     if (!BinaryOperator::isComparisonOp(Opcode))
 710       return false;
 711
 712     // The call site of this function expects the constant on the RHS,
 713     // so change the opcode accordingly.
 714     if (IntegerConstantIsFirstArg)
 715       Opcode = BinaryOperator::reverseComparisonOp(Opcode);
 716
 717     return true;
 718   } else {
 719     return false;
 720   }
 721
 722   if (!retrieveSymbolicExpr(Result, Id, Symbol))
 723     return false;
 724
 725   if (Result.Nodes.getNodeAs<Expr>(SwapId))
 726     Opcode = BinaryOperator::reverseComparisonOp(Opcode);
 727   if (Result.Nodes.getNodeAs<Expr>(NegateId))
 728     Opcode = BinaryOperator::negateComparisonOp(Opcode);
 729   return true;
 730 }
 731
 732 // Checks for expressions like (X == 4) && (Y != 9)
 733 static bool areSidesBinaryConstExpressions(const BinaryOperator *&BinOp, const ASTContext *AstCtx) {
 734   const auto *LhsBinOp = dyn_cast<BinaryOperator>(BinOp->getLHS());
 735   const auto *RhsBinOp = dyn_cast<BinaryOperator>(BinOp->getRHS());
 736
 737   if (!LhsBinOp || !RhsBinOp)
 738     return false;
 739
 740   auto IsIntegerConstantExpr = [AstCtx](const Expr *E) {
 741     return !E->isValueDependent() && E->isIntegerConstantExpr(*AstCtx);
 742   };
 743
 744   if ((IsIntegerConstantExpr(LhsBinOp->getLHS()) ||
 745        IsIntegerConstantExpr(LhsBinOp->getRHS())) &&
 746       (IsIntegerConstantExpr(RhsBinOp->getLHS()) ||
 747        IsIntegerConstantExpr(RhsBinOp->getRHS())))
 748     return true;
 749   return false;
 750 }
 751
 752 // Retrieves integer constant subexpressions from binary operator expressions
 753 // that have two equivalent sides.
 754 // E.g.: from (X == 5) && (X == 5) retrieves 5 and 5.
 755 static bool retrieveConstExprFromBothSides(const BinaryOperator *&BinOp,
 756                                            BinaryOperatorKind &MainOpcode,
 757                                            BinaryOperatorKind &SideOpcode,
 758                                            const Expr *&LhsConst,
 759                                            const Expr *&RhsConst,
 760                                            const ASTContext *AstCtx) {
 761   assert(areSidesBinaryConstExpressions(BinOp, AstCtx) &&
 762          "Both sides of binary operator must be constant expressions!");
 763
 764   MainOpcode = BinOp->getOpcode();
 765
 766   const auto *BinOpLhs = cast<BinaryOperator>(BinOp->getLHS());
 767   const auto *BinOpRhs = cast<BinaryOperator>(BinOp->getRHS());
 768
 769   auto IsIntegerConstantExpr = [AstCtx](const Expr *E) {
 770     return !E->isValueDependent() && E->isIntegerConstantExpr(*AstCtx);
 771   };
 772
 773   LhsConst = IsIntegerConstantExpr(BinOpLhs->getLHS()) ? BinOpLhs->getLHS()
 774                                                        : BinOpLhs->getRHS();
 775   RhsConst = IsIntegerConstantExpr(BinOpRhs->getLHS()) ? BinOpRhs->getLHS()
 776                                                        : BinOpRhs->getRHS();
 777
 778   if (!LhsConst || !RhsConst)
 779     return false;
 780
 781   assert(BinOpLhs->getOpcode() == BinOpRhs->getOpcode() &&
 782          "Sides of the binary operator must be equivalent expressions!");
 783
 784   SideOpcode = BinOpLhs->getOpcode();
 785
 786   return true;
 787 }
 788
 789 static bool isSameRawIdentifierToken(const Token &T1, const Token &T2,
 790                         const SourceManager &SM) {
 791   if (T1.getKind() != T2.getKind())
 792     return false;
 793   if (T1.isNot(tok::raw_identifier))
 794     return true;
 795   if (T1.getLength() != T2.getLength())
 796     return false;
 797   return StringRef(SM.getCharacterData(T1.getLocation()), T1.getLength()) ==
 798          StringRef(SM.getCharacterData(T2.getLocation()), T2.getLength());
 799 }
 800
 801 bool isTokAtEndOfExpr(SourceRange ExprSR, Token T, const SourceManager &SM) {
 802   return SM.getExpansionLoc(ExprSR.getEnd()) == T.getLocation();
 803 }
 804
 805 /// Returns true if both LhsExpr and RhsExpr are
 806 /// macro expressions and they are expanded
 807 /// from different macros.
 808 static bool areExprsFromDifferentMacros(const Expr *LhsExpr,
 809                                         const Expr *RhsExpr,
 810                                         const ASTContext *AstCtx) {
 811   if (!LhsExpr || !RhsExpr)
 812     return false;
 813   SourceRange Lsr = LhsExpr->getSourceRange();
 814   SourceRange Rsr = RhsExpr->getSourceRange();
 815   if (!Lsr.getBegin().isMacroID() || !Rsr.getBegin().isMacroID())
 816     return false;
 817
 818   const SourceManager &SM = AstCtx->getSourceManager();
 819   const LangOptions &LO = AstCtx->getLangOpts();
 820
 821   std::pair<FileID, unsigned> LsrLocInfo =
 822       SM.getDecomposedLoc(SM.getExpansionLoc(Lsr.getBegin()));
 823   std::pair<FileID, unsigned> RsrLocInfo =
 824       SM.getDecomposedLoc(SM.getExpansionLoc(Rsr.getBegin()));
 825   llvm::MemoryBufferRef MB = SM.getBufferOrFake(LsrLocInfo.first);
 826
 827   const char *LTokenPos = MB.getBufferStart() + LsrLocInfo.second;
 828   const char *RTokenPos = MB.getBufferStart() + RsrLocInfo.second;
 829   Lexer LRawLex(SM.getLocForStartOfFile(LsrLocInfo.first), LO,
 830                 MB.getBufferStart(), LTokenPos, MB.getBufferEnd());
 831   Lexer RRawLex(SM.getLocForStartOfFile(RsrLocInfo.first), LO,
 832                 MB.getBufferStart(), RTokenPos, MB.getBufferEnd());
 833
 834   Token LTok, RTok;
 835   do { // Compare the expressions token-by-token.
 836     LRawLex.LexFromRawLexer(LTok);
 837     RRawLex.LexFromRawLexer(RTok);
 838   } while (!LTok.is(tok::eof) && !RTok.is(tok::eof) &&
 839            isSameRawIdentifierToken(LTok, RTok, SM) &&
 840            !isTokAtEndOfExpr(Lsr, LTok, SM) &&
 841            !isTokAtEndOfExpr(Rsr, RTok, SM));
 842   return (!isTokAtEndOfExpr(Lsr, LTok, SM) ||
 843           !isTokAtEndOfExpr(Rsr, RTok, SM)) ||
 844          !isSameRawIdentifierToken(LTok, RTok, SM);
 845 }
 846
 847 static bool areExprsMacroAndNonMacro(const Expr *&LhsExpr,
 848                                      const Expr *&RhsExpr) {
 849   if (!LhsExpr || !RhsExpr)
 850     return false;
 851
 852   SourceLocation LhsLoc = LhsExpr->getExprLoc();
 853   SourceLocation RhsLoc = RhsExpr->getExprLoc();
 854
 855   return LhsLoc.isMacroID() != RhsLoc.isMacroID();
 856 }
 857 } // namespace
 858
 859 void RedundantExpressionCheck::registerMatchers(MatchFinder *Finder) {
 860   const auto AnyLiteralExpr = ignoringParenImpCasts(
 861       anyOf(cxxBoolLiteral(), characterLiteral(), integerLiteral()));
 862
 863   const auto BannedIntegerLiteral =
 864       integerLiteral(expandedByMacro(KnownBannedMacroNames));
 865   const auto BannedAncestor = expr(isRequiresExpr());
 866
 867   // Binary with equivalent operands, like (X != 2 && X != 2).
 868   Finder->addMatcher(
 869       traverse(TK_AsIs,
 870                binaryOperator(
 871                    anyOf(isComparisonOperator(),
 872                          hasAnyOperatorName("-", "/", "%", "|", "&", "^", "&&",
 873                                             "||", "=")),
 874                    operandsAreEquivalent(),
 875                    // Filter noisy false positives.
 876                    unless(isInTemplateInstantiation()),
 877                    unless(binaryOperatorIsInMacro()),
 878                    unless(hasType(realFloatingPointType())),
 879                    unless(hasEitherOperand(hasType(realFloatingPointType()))),
 880                    unless(hasLHS(AnyLiteralExpr)),
 881                    unless(hasDescendant(BannedIntegerLiteral)),
 882                    unless(hasAncestor(BannedAncestor)))
 883                    .bind("binary")),
 884       this);
 885
 886   // Logical or bitwise operator with equivalent nested operands, like (X && Y
 887   // && X) or (X && (Y && X))
 888   Finder->addMatcher(
 889       binaryOperator(hasAnyOperatorName("|", "&", "||", "&&", "^"),
 890                      nestedOperandsAreEquivalent(),
 891                      // Filter noisy false positives.
 892                      unless(isInTemplateInstantiation()),
 893                      unless(binaryOperatorIsInMacro()),
 894                      // TODO: if the banned macros are themselves duplicated
 895                      unless(hasDescendant(BannedIntegerLiteral)),
 896                      unless(hasAncestor(BannedAncestor)))
 897           .bind("nested-duplicates"),
 898       this);
 899
 900   // Conditional (ternary) operator with equivalent operands, like (Y ? X : X).
 901   Finder->addMatcher(
 902       traverse(TK_AsIs,
 903                conditionalOperator(expressionsAreEquivalent(),
 904                                    // Filter noisy false positives.
 905                                    unless(conditionalOperatorIsInMacro()),
 906                                    unless(isInTemplateInstantiation()),
 907                                    unless(hasAncestor(BannedAncestor)))
 908                    .bind("cond")),
 909       this);
 910
 911   // Overloaded operators with equivalent operands.
 912   Finder->addMatcher(
 913       traverse(TK_AsIs,
 914                cxxOperatorCallExpr(
 915                    hasAnyOverloadedOperatorName("-", "/", "%", "|", "&", "^",
 916                                                 "==", "!=", "<", "<=", ">",
 917                                                 ">=", "&&", "||", "="),
 918                    parametersAreEquivalent(),
 919                    // Filter noisy false positives.
 920                    unless(isMacro()), unless(isInTemplateInstantiation()),
 921                    unless(hasAncestor(BannedAncestor)))
 922                    .bind("call")),
 923       this);
 924
 925   // Overloaded operators with equivalent operands.
 926   Finder->addMatcher(
 927       cxxOperatorCallExpr(
 928           hasAnyOverloadedOperatorName("|", "&", "||", "&&", "^"),
 929           nestedParametersAreEquivalent(), argumentCountIs(2),
 930           // Filter noisy false positives.
 931           unless(isMacro()), unless(isInTemplateInstantiation()),
 932           unless(hasAncestor(BannedAncestor)))
 933           .bind("nested-duplicates"),
 934       this);
 935
 936   // Match expressions like: !(1 | 2 | 3)
 937   Finder->addMatcher(
 938       traverse(TK_AsIs,
 939                implicitCastExpr(
 940                    hasImplicitDestinationType(isInteger()),
 941                    has(unaryOperator(
 942                            hasOperatorName("!"),
 943                            hasUnaryOperand(ignoringParenImpCasts(binaryOperator(
 944                                hasAnyOperatorName("|", "&"),
 945                                hasLHS(anyOf(
 946                                    binaryOperator(hasAnyOperatorName("|", "&")),
 947                                    integerLiteral())),
 948                                hasRHS(integerLiteral())))))
 949                            .bind("logical-bitwise-confusion")),
 950                    unless(hasAncestor(BannedAncestor)))),
 951       this);
 952
 953   // Match expressions like: (X << 8) & 0xFF
 954   Finder->addMatcher(
 955       traverse(TK_AsIs,
 956                binaryOperator(
 957                    hasOperatorName("&"),
 958                    hasOperands(ignoringParenImpCasts(binaryOperator(
 959                                    hasOperatorName("<<"),
 960                                    hasRHS(ignoringParenImpCasts(
 961                                        integerLiteral().bind("shift-const"))))),
 962                                ignoringParenImpCasts(
 963                                    integerLiteral().bind("and-const"))),
 964                    unless(hasAncestor(BannedAncestor)))
 965                    .bind("left-right-shift-confusion")),
 966       this);
 967
 968   // Match common expressions and apply more checks to find redundant
 969   // sub-expressions.
 970   //   a) Expr <op> K1 == K2
 971   //   b) Expr <op> K1 == Expr
 972   //   c) Expr <op> K1 == Expr <op> K2
 973   // see: 'checkArithmeticExpr' and 'checkBitwiseExpr'
 974   const auto BinOpCstLeft = matchBinOpIntegerConstantExpr("lhs");
 975   const auto BinOpCstRight = matchBinOpIntegerConstantExpr("rhs");
 976   const auto CstRight = matchIntegerConstantExpr("rhs");
 977   const auto SymRight = matchSymbolicExpr("rhs");
 978
 979   // Match expressions like: x <op> 0xFF == 0xF00.
 980   Finder->addMatcher(
 981       traverse(TK_AsIs, binaryOperator(isComparisonOperator(),
 982                                        hasOperands(BinOpCstLeft, CstRight),
 983                                        unless(hasAncestor(BannedAncestor)))
 984                             .bind("binop-const-compare-to-const")),
 985       this);
 986
 987   // Match expressions like: x <op> 0xFF == x.
 988   Finder->addMatcher(
 989       traverse(
 990           TK_AsIs,
 991           binaryOperator(isComparisonOperator(),
 992                          anyOf(allOf(hasLHS(BinOpCstLeft), hasRHS(SymRight)),
 993                                allOf(hasLHS(SymRight), hasRHS(BinOpCstLeft))),
 994                          unless(hasAncestor(BannedAncestor)))
 995               .bind("binop-const-compare-to-sym")),
 996       this);
 997
 998   // Match expressions like: x <op> 10 == x <op> 12.
 999   Finder->addMatcher(
1000       traverse(TK_AsIs,
1001                binaryOperator(isComparisonOperator(), hasLHS(BinOpCstLeft),
1002                               hasRHS(BinOpCstRight),
1003                               // Already reported as redundant.
1004                               unless(operandsAreEquivalent()),
1005                               unless(hasAncestor(BannedAncestor)))
1006                    .bind("binop-const-compare-to-binop-const")),
1007       this);
1008
1009   // Match relational expressions combined with logical operators and find
1010   // redundant sub-expressions.
1011   // see: 'checkRelationalExpr'
1012
1013   // Match expressions like: x < 2 && x > 2.
1014   const auto ComparisonLeft = matchRelationalIntegerConstantExpr("lhs");
1015   const auto ComparisonRight = matchRelationalIntegerConstantExpr("rhs");
1016   Finder->addMatcher(
1017       traverse(TK_AsIs,
1018                binaryOperator(hasAnyOperatorName("||", "&&"),
1019                               hasLHS(ComparisonLeft), hasRHS(ComparisonRight),
1020                               // Already reported as redundant.
1021                               unless(operandsAreEquivalent()),
1022                               unless(hasAncestor(BannedAncestor)))
1023                    .bind("comparisons-of-symbol-and-const")),
1024       this);
1025 }
1026
1027 void RedundantExpressionCheck::checkArithmeticExpr(
1028     const MatchFinder::MatchResult &Result) {
1029   APSInt LhsValue, RhsValue;
1030   const Expr *LhsSymbol = nullptr, *RhsSymbol = nullptr;
1031   BinaryOperatorKind LhsOpcode, RhsOpcode;
1032
1033   if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1034           "binop-const-compare-to-sym")) {
1035     BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1036     if (!retrieveBinOpIntegerConstantExpr(Result, "lhs", LhsOpcode, LhsSymbol,
1037                                           LhsValue) ||
1038         !retrieveSymbolicExpr(Result, "rhs", RhsSymbol) ||
1039         !areEquivalentExpr(LhsSymbol, RhsSymbol))
1040       return;
1041
1042     // Check expressions: x + k == x  or  x - k == x.
1043     if (LhsOpcode == BO_Add || LhsOpcode == BO_Sub) {
1044       if ((LhsValue != 0 && Opcode == BO_EQ) ||
1045           (LhsValue == 0 && Opcode == BO_NE))
1046         diag(ComparisonOperator->getOperatorLoc(),
1047              "logical expression is always false");
1048       else if ((LhsValue == 0 && Opcode == BO_EQ) ||
1049                (LhsValue != 0 && Opcode == BO_NE))
1050         diag(ComparisonOperator->getOperatorLoc(),
1051              "logical expression is always true");
1052     }
1053   } else if (const auto *ComparisonOperator =
1054                  Result.Nodes.getNodeAs<BinaryOperator>(
1055                      "binop-const-compare-to-binop-const")) {
1056     BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1057
1058     if (!retrieveBinOpIntegerConstantExpr(Result, "lhs", LhsOpcode, LhsSymbol,
1059                                           LhsValue) ||
1060         !retrieveBinOpIntegerConstantExpr(Result, "rhs", RhsOpcode, RhsSymbol,
1061                                           RhsValue) ||
1062         !areEquivalentExpr(LhsSymbol, RhsSymbol))
1063       return;
1064
1065     transformSubToCanonicalAddExpr(LhsOpcode, LhsValue);
1066     transformSubToCanonicalAddExpr(RhsOpcode, RhsValue);
1067
1068     // Check expressions: x + 1 == x + 2  or  x + 1 != x + 2.
1069     if (LhsOpcode == BO_Add && RhsOpcode == BO_Add) {
1070       if ((Opcode == BO_EQ && APSInt::compareValues(LhsValue, RhsValue) == 0) ||
1071           (Opcode == BO_NE && APSInt::compareValues(LhsValue, RhsValue) != 0)) {
1072         diag(ComparisonOperator->getOperatorLoc(),
1073              "logical expression is always true");
1074       } else if ((Opcode == BO_EQ &&
1075                   APSInt::compareValues(LhsValue, RhsValue) != 0) ||
1076                  (Opcode == BO_NE &&
1077                   APSInt::compareValues(LhsValue, RhsValue) == 0)) {
1078         diag(ComparisonOperator->getOperatorLoc(),
1079              "logical expression is always false");
1080       }
1081     }
1082   }
1083 }
1084
1085 static bool exprEvaluatesToZero(BinaryOperatorKind Opcode, APSInt Value) {
1086   return (Opcode == BO_And || Opcode == BO_AndAssign) && Value == 0;
1087 }
1088
1089 static bool exprEvaluatesToBitwiseNegatedZero(BinaryOperatorKind Opcode,
1090                                               APSInt Value) {
1091   return (Opcode == BO_Or || Opcode == BO_OrAssign) && ~Value == 0;
1092 }
1093
1094 static bool exprEvaluatesToSymbolic(BinaryOperatorKind Opcode, APSInt Value) {
1095   return ((Opcode == BO_Or || Opcode == BO_OrAssign) && Value == 0) ||
1096          ((Opcode == BO_And || Opcode == BO_AndAssign) && ~Value == 0);
1097 }
1098
1099
1100 void RedundantExpressionCheck::checkBitwiseExpr(
1101     const MatchFinder::MatchResult &Result) {
1102   if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1103           "binop-const-compare-to-const")) {
1104     BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1105
1106     APSInt LhsValue, RhsValue;
1107     const Expr *LhsSymbol = nullptr;
1108     BinaryOperatorKind LhsOpcode;
1109     if (!retrieveBinOpIntegerConstantExpr(Result, "lhs", LhsOpcode, LhsSymbol,
1110                                           LhsValue) ||
1111         !retrieveIntegerConstantExpr(Result, "rhs", RhsValue))
1112       return;
1113
1114     uint64_t LhsConstant = LhsValue.getZExtValue();
1115     uint64_t RhsConstant = RhsValue.getZExtValue();
1116     SourceLocation Loc = ComparisonOperator->getOperatorLoc();
1117
1118     // Check expression: x & k1 == k2  (i.e. x & 0xFF == 0xF00)
1119     if (LhsOpcode == BO_And && (LhsConstant & RhsConstant) != RhsConstant) {
1120       if (Opcode == BO_EQ)
1121         diag(Loc, "logical expression is always false");
1122       else if (Opcode == BO_NE)
1123         diag(Loc, "logical expression is always true");
1124     }
1125
1126     // Check expression: x | k1 == k2  (i.e. x | 0xFF == 0xF00)
1127     if (LhsOpcode == BO_Or && (LhsConstant | RhsConstant) != RhsConstant) {
1128       if (Opcode == BO_EQ)
1129         diag(Loc, "logical expression is always false");
1130       else if (Opcode == BO_NE)
1131         diag(Loc, "logical expression is always true");
1132     }
1133   } else if (const auto *IneffectiveOperator =
1134                  Result.Nodes.getNodeAs<BinaryOperator>(
1135                      "ineffective-bitwise")) {
1136     APSInt Value;
1137     const Expr *Sym = nullptr, *ConstExpr = nullptr;
1138
1139     if (!retrieveSymbolicExpr(Result, "ineffective-bitwise", Sym) ||
1140         !retrieveIntegerConstantExpr(Result, "ineffective-bitwise", Value,
1141                                      ConstExpr))
1142       return;
1143
1144     if((Value != 0 && ~Value != 0) || Sym->getExprLoc().isMacroID())
1145         return;
1146
1147     SourceLocation Loc = IneffectiveOperator->getOperatorLoc();
1148
1149     BinaryOperatorKind Opcode = IneffectiveOperator->getOpcode();
1150     if (exprEvaluatesToZero(Opcode, Value)) {
1151       diag(Loc, "expression always evaluates to 0");
1152     } else if (exprEvaluatesToBitwiseNegatedZero(Opcode, Value)) {
1153       SourceRange ConstExprRange(ConstExpr->getBeginLoc(),
1154                                  ConstExpr->getEndLoc());
1155       StringRef ConstExprText = Lexer::getSourceText(
1156           CharSourceRange::getTokenRange(ConstExprRange), *Result.SourceManager,
1157           Result.Context->getLangOpts());
1158
1159       diag(Loc, "expression always evaluates to '%0'") << ConstExprText;
1160
1161     } else if (exprEvaluatesToSymbolic(Opcode, Value)) {
1162       SourceRange SymExprRange(Sym->getBeginLoc(), Sym->getEndLoc());
1163
1164       StringRef ExprText = Lexer::getSourceText(
1165           CharSourceRange::getTokenRange(SymExprRange), *Result.SourceManager,
1166           Result.Context->getLangOpts());
1167
1168       diag(Loc, "expression always evaluates to '%0'") << ExprText;
1169     }
1170   }
1171 }
1172
1173 void RedundantExpressionCheck::checkRelationalExpr(
1174     const MatchFinder::MatchResult &Result) {
1175   if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1176           "comparisons-of-symbol-and-const")) {
1177     // Matched expressions are: (x <op> k1) <REL> (x <op> k2).
1178     // E.g.: (X < 2) && (X > 4)
1179     BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1180
1181     const Expr *LhsExpr = nullptr, *RhsExpr = nullptr;
1182     const Expr *LhsSymbol = nullptr, *RhsSymbol = nullptr;
1183     const Expr *LhsConst = nullptr, *RhsConst = nullptr;
1184     BinaryOperatorKind LhsOpcode, RhsOpcode;
1185     APSInt LhsValue, RhsValue;
1186
1187     if (!retrieveRelationalIntegerConstantExpr(
1188             Result, "lhs", LhsExpr, LhsOpcode, LhsSymbol, LhsValue, LhsConst) ||
1189         !retrieveRelationalIntegerConstantExpr(
1190             Result, "rhs", RhsExpr, RhsOpcode, RhsSymbol, RhsValue, RhsConst) ||
1191         !areEquivalentExpr(LhsSymbol, RhsSymbol))
1192       return;
1193
1194     // Bring expr to a canonical form: smallest constant must be on the left.
1195     if (APSInt::compareValues(LhsValue, RhsValue) > 0) {
1196       std::swap(LhsExpr, RhsExpr);
1197       std::swap(LhsValue, RhsValue);
1198       std::swap(LhsSymbol, RhsSymbol);
1199       std::swap(LhsOpcode, RhsOpcode);
1200     }
1201
1202     // Constants come from two different macros, or one of them is a macro.
1203     if (areExprsFromDifferentMacros(LhsConst, RhsConst, Result.Context) ||
1204         areExprsMacroAndNonMacro(LhsConst, RhsConst))
1205       return;
1206
1207     if ((Opcode == BO_LAnd || Opcode == BO_LOr) &&
1208         areEquivalentRanges(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1209       diag(ComparisonOperator->getOperatorLoc(),
1210            "equivalent expression on both sides of logical operator");
1211       return;
1212     }
1213
1214     if (Opcode == BO_LAnd) {
1215       if (areExclusiveRanges(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1216         diag(ComparisonOperator->getOperatorLoc(),
1217              "logical expression is always false");
1218       } else if (rangeSubsumesRange(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1219         diag(LhsExpr->getExprLoc(), "expression is redundant");
1220       } else if (rangeSubsumesRange(RhsOpcode, RhsValue, LhsOpcode, LhsValue)) {
1221         diag(RhsExpr->getExprLoc(), "expression is redundant");
1222       }
1223     }
1224
1225     if (Opcode == BO_LOr) {
1226       if (rangesFullyCoverDomain(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1227         diag(ComparisonOperator->getOperatorLoc(),
1228              "logical expression is always true");
1229       } else if (rangeSubsumesRange(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1230         diag(RhsExpr->getExprLoc(), "expression is redundant");
1231       } else if (rangeSubsumesRange(RhsOpcode, RhsValue, LhsOpcode, LhsValue)) {
1232         diag(LhsExpr->getExprLoc(), "expression is redundant");
1233       }
1234     }
1235   }
1236 }
1237
1238 void RedundantExpressionCheck::check(const MatchFinder::MatchResult &Result) {
1239   if (const auto *BinOp = Result.Nodes.getNodeAs<BinaryOperator>("binary")) {
1240     // If the expression's constants are macros, check whether they are
1241     // intentional.
1242     if (areSidesBinaryConstExpressions(BinOp, Result.Context)) {
1243       const Expr *LhsConst = nullptr, *RhsConst = nullptr;
1244       BinaryOperatorKind MainOpcode, SideOpcode;
1245
1246       if (!retrieveConstExprFromBothSides(BinOp, MainOpcode, SideOpcode,
1247                                           LhsConst, RhsConst, Result.Context))
1248         return;
1249
1250       if (areExprsFromDifferentMacros(LhsConst, RhsConst, Result.Context) ||
1251           areExprsMacroAndNonMacro(LhsConst, RhsConst))
1252         return;
1253     }
1254
1255     diag(BinOp->getOperatorLoc(), "both sides of operator are equivalent");
1256   }
1257
1258   if (const auto *CondOp =
1259           Result.Nodes.getNodeAs<ConditionalOperator>("cond")) {
1260     const Expr *TrueExpr = CondOp->getTrueExpr();
1261     const Expr *FalseExpr = CondOp->getFalseExpr();
1262
1263     if (areExprsFromDifferentMacros(TrueExpr, FalseExpr, Result.Context) ||
1264         areExprsMacroAndNonMacro(TrueExpr, FalseExpr))
1265       return;
1266     diag(CondOp->getColonLoc(),
1267          "'true' and 'false' expressions are equivalent");
1268   }
1269
1270   if (const auto *Call = Result.Nodes.getNodeAs<CXXOperatorCallExpr>("call")) {
1271     if (canOverloadedOperatorArgsBeModified(Call, true))
1272       return;
1273
1274     diag(Call->getOperatorLoc(),
1275          "both sides of overloaded operator are equivalent");
1276   }
1277
1278   if (const auto *Op = Result.Nodes.getNodeAs<Expr>("nested-duplicates")) {
1279     const auto *Call = dyn_cast<CXXOperatorCallExpr>(Op);
1280     if (Call && canOverloadedOperatorArgsBeModified(Call, true))
1281       return;
1282
1283     StringRef Message =
1284         Call ? "overloaded operator has equivalent nested operands"
1285              : "operator has equivalent nested operands";
1286
1287     const auto Diag = diag(Op->getExprLoc(), Message);
1288     for (const auto &KeyValue : Result.Nodes.getMap()) {
1289       if (StringRef(KeyValue.first).startswith("duplicate"))
1290         Diag << KeyValue.second.getSourceRange();
1291     }
1292   }
1293
1294   if (const auto *NegateOperator =
1295           Result.Nodes.getNodeAs<UnaryOperator>("logical-bitwise-confusion")) {
1296     SourceLocation OperatorLoc = NegateOperator->getOperatorLoc();
1297
1298     auto Diag =
1299         diag(OperatorLoc,
1300              "ineffective logical negation operator used; did you mean '~'?");
1301     SourceLocation LogicalNotLocation = OperatorLoc.getLocWithOffset(1);
1302
1303     if (!LogicalNotLocation.isMacroID())
1304       Diag << FixItHint::CreateReplacement(
1305           CharSourceRange::getCharRange(OperatorLoc, LogicalNotLocation), "~");
1306   }
1307
1308   if (const auto *BinaryAndExpr = Result.Nodes.getNodeAs<BinaryOperator>(
1309           "left-right-shift-confusion")) {
1310     const auto *ShiftingConst = Result.Nodes.getNodeAs<Expr>("shift-const");
1311     assert(ShiftingConst && "Expr* 'ShiftingConst' is nullptr!");
1312     std::optional<llvm::APSInt> ShiftingValue =
1313         ShiftingConst->getIntegerConstantExpr(*Result.Context);
1314
1315     if (!ShiftingValue)
1316       return;
1317
1318     const auto *AndConst = Result.Nodes.getNodeAs<Expr>("and-const");
1319     assert(AndConst && "Expr* 'AndCont' is nullptr!");
1320     std::optional<llvm::APSInt> AndValue =
1321         AndConst->getIntegerConstantExpr(*Result.Context);
1322     if (!AndValue)
1323       return;
1324
1325     // If ShiftingConst is shifted left with more bits than the position of the
1326     // leftmost 1 in the bit representation of AndValue, AndConstant is
1327     // ineffective.
1328     if (AndValue->getActiveBits() > *ShiftingValue)
1329       return;
1330
1331     auto Diag = diag(BinaryAndExpr->getOperatorLoc(),
1332                      "ineffective bitwise and operation");
1333   }
1334
1335   // Check for the following bound expressions:
1336   // - "binop-const-compare-to-sym",
1337   // - "binop-const-compare-to-binop-const",
1338   // Produced message:
1339   // -> "logical expression is always false/true"
1340   checkArithmeticExpr(Result);
1341
1342   // Check for the following bound expression:
1343   // - "binop-const-compare-to-const",
1344   // - "ineffective-bitwise"
1345   // Produced message:
1346   // -> "logical expression is always false/true"
1347   // -> "expression always evaluates to ..."
1348   checkBitwiseExpr(Result);
1349
1350   // Check for te following bound expression:
1351   // - "comparisons-of-symbol-and-const",
1352   // Produced messages:
1353   // -> "equivalent expression on both sides of logical operator",
1354   // -> "logical expression is always false/true"
1355   // -> "expression is redundant"
1356   checkRelationalExpr(Result);
1357 }
1358
1359 } // namespace clang::tidy::misc