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