10 #include "../utils/Matchers.h"
11 #include "../utils/OptionsUtils.h"
12 #include "clang/AST/ASTContext.h"
13 #include "clang/ASTMatchers/ASTMatchFinder.h"
14 #include "clang/Basic/LLVM.h"
15 #include "clang/Basic/SourceLocation.h"
16 #include "clang/Basic/SourceManager.h"
17 #include "clang/Lex/Lexer.h"
18 #include "llvm/ADT/APInt.h"
19 #include "llvm/ADT/APSInt.h"
20 #include "llvm/ADT/FoldingSet.h"
21 #include "llvm/ADT/SmallBitVector.h"
22 #include "llvm/Support/Casting.h"
23 #include "llvm/Support/FormatVariadic.h"
39 static constexpr llvm::StringLiteral KnownBannedMacroNames[] = {
46 static bool incrementWithoutOverflow(
const APSInt &Value, APSInt &Result) {
49 return Value < Result;
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;
60 static bool areEquivalentExpr(
const Expr *Left,
const Expr *Right) {
68 if (
Left->getStmtClass() !=
Right->getStmtClass())
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)))
81 if (LeftIter !=
Left->child_end() || RightIter !=
Right->child_end())
85 switch (
Left->getStmtClass()) {
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() &&
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())
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:
131 case Stmt::UnaryOperatorClass:
132 if (cast<UnaryOperator>(Left)->isIncrementDecrementOp())
134 return cast<UnaryOperator>(Left)->getOpcode() ==
135 cast<UnaryOperator>(Right)->getOpcode();
136 case Stmt::BinaryOperatorClass:
137 if (cast<BinaryOperator>(Left)->isAssignmentOp())
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->getArgumentType() ==
148 RightUnaryExpr->getArgumentType();
149 if (!LeftUnaryExpr->isArgumentType() && !RightUnaryExpr->isArgumentType())
150 return areEquivalentExpr(LeftUnaryExpr->getArgumentExpr(),
151 RightUnaryExpr->getArgumentExpr());
159 static bool areEquivalentRanges(BinaryOperatorKind OpcodeLHS,
160 const APSInt &ValueLHS,
161 BinaryOperatorKind OpcodeRHS,
162 const APSInt &ValueRHS) {
163 assert(APSInt::compareValues(ValueLHS, ValueRHS) <= 0 &&
164 "Values must be ordered");
166 if (APSInt::compareValues(ValueLHS, ValueRHS) == 0)
167 return OpcodeLHS == OpcodeRHS;
170 APSInt ValueLhsPlus1;
171 return ((OpcodeLHS == BO_LE && OpcodeRHS == BO_LT) ||
172 (OpcodeLHS == BO_GT && OpcodeRHS == BO_GE)) &&
173 incrementWithoutOverflow(ValueLHS, ValueLhsPlus1) &&
174 APSInt::compareValues(ValueLhsPlus1, ValueRHS) == 0;
179 static bool areExclusiveRanges(BinaryOperatorKind OpcodeLHS,
180 const APSInt &ValueLHS,
181 BinaryOperatorKind OpcodeRHS,
182 const APSInt &ValueRHS) {
183 assert(APSInt::compareValues(ValueLHS, ValueRHS) <= 0 &&
184 "Values must be ordered");
187 if (APSInt::compareValues(ValueLHS, ValueRHS) == 0) {
190 return OpcodeRHS == BO_NE || OpcodeRHS == BO_GT || OpcodeRHS == BO_LT;
192 return OpcodeRHS == BO_EQ;
194 return OpcodeRHS == BO_GT;
196 return OpcodeRHS == BO_LT;
198 return OpcodeRHS == BO_EQ || OpcodeRHS == BO_GT || OpcodeRHS == BO_GE;
200 return OpcodeRHS == BO_EQ || OpcodeRHS == BO_LT || OpcodeRHS == BO_LE;
207 if ((OpcodeLHS == BO_EQ || OpcodeLHS == BO_LT || OpcodeLHS == BO_LE) &&
208 (OpcodeRHS == BO_EQ || OpcodeRHS == BO_GT || OpcodeRHS == BO_GE))
212 APSInt ValueLhsPlus1;
213 if (OpcodeLHS == BO_GT && OpcodeRHS == BO_LT &&
214 incrementWithoutOverflow(ValueLHS, ValueLhsPlus1) &&
215 APSInt::compareValues(ValueLhsPlus1, ValueRHS) == 0)
223 static bool rangesFullyCoverDomain(BinaryOperatorKind OpcodeLHS,
224 const APSInt &ValueLHS,
225 BinaryOperatorKind OpcodeRHS,
226 const APSInt &ValueRHS) {
227 assert(APSInt::compareValues(ValueLHS, ValueRHS) <= 0 &&
228 "Values must be ordered");
231 if (APSInt::compareValues(ValueLHS, ValueRHS) == 0) {
234 return OpcodeRHS == BO_NE;
236 return OpcodeRHS == BO_EQ;
238 return OpcodeRHS == BO_GT || OpcodeRHS == BO_GE;
240 return OpcodeRHS == BO_GE;
242 return OpcodeRHS == BO_LT || OpcodeRHS == BO_LE;
244 return OpcodeRHS == BO_LE;
251 APSInt ValueLhsPlus1;
252 if (OpcodeLHS == BO_LE && OpcodeRHS == BO_GE &&
253 incrementWithoutOverflow(ValueLHS, ValueLhsPlus1) &&
254 APSInt::compareValues(ValueLhsPlus1, ValueRHS) == 0)
258 if ((OpcodeLHS == BO_GT || OpcodeLHS == BO_GE) &&
259 (OpcodeRHS == BO_LT || OpcodeRHS == BO_LE))
264 if (OpcodeLHS == BO_NE && OpcodeRHS == BO_NE)
270 static bool rangeSubsumesRange(BinaryOperatorKind OpcodeLHS,
271 const APSInt &ValueLHS,
272 BinaryOperatorKind OpcodeRHS,
273 const APSInt &ValueRHS) {
274 int Comparison = APSInt::compareValues(ValueLHS, ValueRHS);
277 return OpcodeRHS == BO_EQ && Comparison == 0;
279 return (OpcodeRHS == BO_NE && Comparison == 0) ||
280 (OpcodeRHS == BO_EQ && Comparison != 0) ||
281 (OpcodeRHS == BO_LT && Comparison >= 0) ||
282 (OpcodeRHS == BO_LE && Comparison > 0) ||
283 (OpcodeRHS == BO_GT && Comparison <= 0) ||
284 (OpcodeRHS == BO_GE && Comparison < 0);
287 return ((OpcodeRHS == BO_LT && Comparison >= 0) ||
288 (OpcodeRHS == BO_LE && Comparison > 0) ||
289 (OpcodeRHS == BO_EQ && Comparison > 0));
291 return ((OpcodeRHS == BO_GT && Comparison <= 0) ||
292 (OpcodeRHS == BO_GE && Comparison < 0) ||
293 (OpcodeRHS == BO_EQ && Comparison < 0));
295 return (OpcodeRHS == BO_LT || OpcodeRHS == BO_LE || OpcodeRHS == BO_EQ) &&
298 return (OpcodeRHS == BO_GT || OpcodeRHS == BO_GE || OpcodeRHS == BO_EQ) &&
305 static void transformSubToCanonicalAddExpr(BinaryOperatorKind &Opcode,
307 if (Opcode == BO_Sub) {
314 static OverloadedOperatorKind getOp(
const BinaryOperator *Op) {
315 return BinaryOperator::getOverloadedOperator(Op->getOpcode());
318 static OverloadedOperatorKind getOp(
const CXXOperatorCallExpr *Op) {
319 if (Op->getNumArgs() != 2)
321 return Op->getOperator();
324 static std::pair<const Expr *, const Expr *>
325 getOperands(
const BinaryOperator *Op) {
326 return {Op->getLHS()->IgnoreParenImpCasts(),
327 Op->getRHS()->IgnoreParenImpCasts()};
330 static std::pair<const Expr *, const Expr *>
331 getOperands(
const CXXOperatorCallExpr *Op) {
332 return {Op->getArg(0)->IgnoreParenImpCasts(),
333 Op->getArg(1)->IgnoreParenImpCasts()};
336 template <
typename TExpr>
337 static const TExpr *checkOpKind(
const Expr *TheExpr,
338 OverloadedOperatorKind OpKind) {
339 const auto *AsTExpr = dyn_cast_or_null<TExpr>(TheExpr);
340 if (AsTExpr && getOp(AsTExpr) == OpKind)
348 template <
typename TExpr,
unsigned N>
349 static bool collectOperands(
const Expr *Part,
350 SmallVector<const Expr *, N> &AllOperands,
351 OverloadedOperatorKind OpKind) {
352 if (
const auto *BinOp = checkOpKind<TExpr>(Part, OpKind)) {
353 const std::pair<const Expr *, const Expr *> Operands = getOperands(BinOp);
354 if (areEquivalentExpr(Operands.first, Operands.second))
356 return collectOperands<TExpr>(Operands.first, AllOperands, OpKind) ||
357 collectOperands<TExpr>(Operands.second, AllOperands, OpKind);
360 AllOperands.push_back(Part);
364 template <
typename TExpr>
365 static bool hasSameOperatorParent(
const Expr *TheExpr,
366 OverloadedOperatorKind OpKind,
367 ASTContext &Context) {
369 const DynTypedNodeList
Parents = Context.getParents(*TheExpr);
370 for (DynTypedNode DynParent : Parents) {
371 if (
const auto *
Parent = DynParent.get<Expr>()) {
372 bool Skip = isa<ParenExpr>(
Parent) || isa<ImplicitCastExpr>(
Parent) ||
374 isa<MaterializeTemporaryExpr>(
Parent);
375 if (Skip && hasSameOperatorParent<TExpr>(
Parent, OpKind, Context))
377 if (checkOpKind<TExpr>(
Parent, OpKind))
385 template <
typename TExpr>
387 markDuplicateOperands(
const TExpr *TheExpr,
388 ast_matchers::internal::BoundNodesTreeBuilder *
Builder,
389 ASTContext &Context) {
390 const OverloadedOperatorKind OpKind = getOp(TheExpr);
391 if (OpKind == OO_None)
395 const std::pair<const Expr *, const Expr *> Operands = getOperands(TheExpr);
396 if (!(checkOpKind<TExpr>(Operands.first, OpKind) ||
397 checkOpKind<TExpr>(Operands.second, OpKind)))
402 if (hasSameOperatorParent<TExpr>(TheExpr, OpKind, Context))
405 SmallVector<const Expr *, 4> AllOperands;
406 if (collectOperands<TExpr>(Operands.first, AllOperands, OpKind))
408 if (collectOperands<TExpr>(Operands.second, AllOperands, OpKind))
410 size_t NumOperands = AllOperands.size();
411 llvm::SmallBitVector Duplicates(NumOperands);
412 for (
size_t I = 0; I < NumOperands; I++) {
415 bool FoundDuplicates =
false;
417 for (
size_t J = I + 1; J < NumOperands; J++) {
418 if (AllOperands[J]->HasSideEffects(Context))
421 if (areEquivalentExpr(AllOperands[I], AllOperands[J])) {
422 FoundDuplicates =
true;
424 Builder->setBinding(SmallString<11>(llvm::formatv(
"duplicate{0}", J)),
425 DynTypedNode::create(*AllOperands[J]));
430 Builder->setBinding(SmallString<11>(llvm::formatv(
"duplicate{0}", I)),
431 DynTypedNode::create(*AllOperands[I]));
434 return Duplicates.any();
438 if (Node.isInstantiationDependent())
440 return Node.isIntegerConstantExpr(Finder->getASTContext());
443 AST_MATCHER(BinaryOperator, operandsAreEquivalent) {
444 return areEquivalentExpr(Node.getLHS(), Node.getRHS());
447 AST_MATCHER(BinaryOperator, nestedOperandsAreEquivalent) {
448 return markDuplicateOperands(&Node,
Builder, Finder->getASTContext());
451 AST_MATCHER(ConditionalOperator, expressionsAreEquivalent) {
452 return areEquivalentExpr(Node.getTrueExpr(), Node.getFalseExpr());
456 return Node.getNumArgs() == 2 &&
457 areEquivalentExpr(Node.getArg(0), Node.getArg(1));
460 AST_MATCHER(CXXOperatorCallExpr, nestedParametersAreEquivalent) {
461 return markDuplicateOperands(&Node,
Builder, Finder->getASTContext());
464 AST_MATCHER(BinaryOperator, binaryOperatorIsInMacro) {
465 return Node.getOperatorLoc().isMacroID();
468 AST_MATCHER(ConditionalOperator, conditionalOperatorIsInMacro) {
469 return Node.getQuestionLoc().isMacroID() || Node.getColonLoc().isMacroID();
472 AST_MATCHER(Expr, isMacro) {
return Node.getExprLoc().isMacroID(); }
474 AST_MATCHER_P(Expr, expandedByMacro, ArrayRef<llvm::StringLiteral>, Names) {
475 const SourceManager &SM = Finder->getASTContext().getSourceManager();
476 const LangOptions &LO = Finder->getASTContext().getLangOpts();
477 SourceLocation
Loc = Node.getExprLoc();
478 while (
Loc.isMacroID()) {
479 StringRef MacroName = Lexer::getImmediateMacroName(
Loc, SM, LO);
480 if (llvm::is_contained(Names, MacroName))
482 Loc = SM.getImmediateMacroCallerLoc(
Loc);
488 static ast_matchers::internal::Matcher<Expr>
489 matchIntegerConstantExpr(StringRef Id) {
490 std::string CstId = (Id +
"-const").str();
491 return expr(isIntegerConstantExpr()).bind(CstId);
497 static bool retrieveIntegerConstantExpr(
const MatchFinder::MatchResult &Result,
498 StringRef Id, APSInt &Value,
499 const Expr *&ConstExpr) {
500 std::string CstId = (Id +
"-const").str();
501 ConstExpr = Result.Nodes.getNodeAs<Expr>(CstId);
504 Optional<llvm::APSInt> R = ConstExpr->getIntegerConstantExpr(*Result.Context);
512 static bool retrieveIntegerConstantExpr(
const MatchFinder::MatchResult &Result,
513 StringRef Id, APSInt &Value) {
514 const Expr *ConstExpr =
nullptr;
515 return retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr);
520 static ast_matchers::internal::Matcher<Expr> matchSymbolicExpr(StringRef Id) {
521 std::string SymId = (Id +
"-sym").str();
522 return ignoringParenImpCasts(
523 expr(unless(isIntegerConstantExpr())).bind(SymId));
528 static bool retrieveSymbolicExpr(
const MatchFinder::MatchResult &Result,
529 StringRef Id,
const Expr *&SymExpr) {
530 std::string SymId = (Id +
"-sym").str();
531 if (
const auto *Node = Result.Nodes.getNodeAs<Expr>(SymId)) {
540 static ast_matchers::internal::Matcher<Expr>
541 matchBinOpIntegerConstantExpr(StringRef Id) {
542 const auto BinOpCstExpr =
543 expr(anyOf(binaryOperator(hasAnyOperatorName(
"+",
"|",
"&"),
544 hasOperands(matchSymbolicExpr(Id),
545 matchIntegerConstantExpr(Id))),
546 binaryOperator(hasOperatorName(
"-"),
547 hasLHS(matchSymbolicExpr(Id)),
548 hasRHS(matchIntegerConstantExpr(Id)))))
550 return ignoringParenImpCasts(BinOpCstExpr);
556 retrieveBinOpIntegerConstantExpr(
const MatchFinder::MatchResult &Result,
557 StringRef Id, BinaryOperatorKind &Opcode,
558 const Expr *&Symbol, APSInt &Value) {
559 if (
const auto *BinExpr = Result.Nodes.getNodeAs<BinaryOperator>(Id)) {
560 Opcode = BinExpr->getOpcode();
561 return retrieveSymbolicExpr(Result, Id, Symbol) &&
562 retrieveIntegerConstantExpr(Result, Id, Value);
568 static ast_matchers::internal::Matcher<Expr>
569 matchRelationalIntegerConstantExpr(StringRef Id) {
570 std::string CastId = (Id +
"-cast").str();
571 std::string SwapId = (Id +
"-swap").str();
572 std::string NegateId = (Id +
"-negate").str();
573 std::string OverloadId = (Id +
"-overload").str();
574 std::string ConstId = (Id +
"-const").str();
576 const auto RelationalExpr = ignoringParenImpCasts(binaryOperator(
577 isComparisonOperator(), expr().bind(Id),
578 anyOf(allOf(hasLHS(matchSymbolicExpr(Id)),
579 hasRHS(matchIntegerConstantExpr(Id))),
580 allOf(hasLHS(matchIntegerConstantExpr(Id)),
581 hasRHS(matchSymbolicExpr(Id)), expr().bind(SwapId)))));
585 const auto CastExpr =
586 implicitCastExpr(hasCastKind(CK_IntegralToBoolean),
587 hasSourceExpression(matchSymbolicExpr(Id)))
590 const auto NegateRelationalExpr =
591 unaryOperator(hasOperatorName(
"!"),
592 hasUnaryOperand(anyOf(CastExpr, RelationalExpr)))
596 const auto NegateNegateRelationalExpr =
597 unaryOperator(hasOperatorName(
"!"),
598 hasUnaryOperand(unaryOperator(
599 hasOperatorName(
"!"),
600 hasUnaryOperand(anyOf(CastExpr, RelationalExpr)))));
602 const auto OverloadedOperatorExpr =
604 hasAnyOverloadedOperatorName(
"==",
"!=",
"<",
"<=",
">",
">="),
606 unless(isMacro()), unless(isInTemplateInstantiation()),
607 anyOf(hasLHS(ignoringParenImpCasts(integerLiteral().bind(ConstId))),
608 hasRHS(ignoringParenImpCasts(integerLiteral().bind(ConstId)))))
611 return anyOf(RelationalExpr, CastExpr, NegateRelationalExpr,
612 NegateNegateRelationalExpr, OverloadedOperatorExpr);
617 static bool isNonConstReferenceType(QualType ParamType) {
618 return ParamType->isReferenceType() &&
619 !ParamType.getNonReferenceType().isConstQualified();
629 canOverloadedOperatorArgsBeModified(
const CXXOperatorCallExpr *OperatorCall,
630 bool CheckSecondParam) {
631 const auto *OperatorDecl =
632 dyn_cast_or_null<FunctionDecl>(OperatorCall->getCalleeDecl());
638 unsigned ParamCount = OperatorDecl->getNumParams();
643 if (ParamCount == 1 &&
644 !OperatorDecl->getType()->castAs<FunctionType>()->isConst())
647 if (isNonConstReferenceType(OperatorDecl->getParamDecl(0)->getType()))
650 return CheckSecondParam && ParamCount == 2 &&
651 isNonConstReferenceType(OperatorDecl->getParamDecl(1)->getType());
656 static bool retrieveRelationalIntegerConstantExpr(
657 const MatchFinder::MatchResult &Result, StringRef Id,
658 const Expr *&OperandExpr, BinaryOperatorKind &Opcode,
const Expr *&Symbol,
659 APSInt &Value,
const Expr *&ConstExpr) {
660 std::string CastId = (Id +
"-cast").str();
661 std::string SwapId = (Id +
"-swap").str();
662 std::string NegateId = (Id +
"-negate").str();
663 std::string OverloadId = (Id +
"-overload").str();
665 if (
const auto *Bin = Result.Nodes.getNodeAs<BinaryOperator>(Id)) {
667 Opcode = Bin->getOpcode();
670 if (!retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr))
672 }
else if (
const auto *Cast = Result.Nodes.getNodeAs<CastExpr>(CastId)) {
676 Value = APSInt(32,
false);
677 }
else if (
const auto *OverloadedOperatorExpr =
678 Result.Nodes.getNodeAs<CXXOperatorCallExpr>(OverloadId)) {
679 if (canOverloadedOperatorArgsBeModified(OverloadedOperatorExpr,
false))
682 bool IntegerConstantIsFirstArg =
false;
684 if (
const auto *Arg = OverloadedOperatorExpr->getArg(1)) {
685 if (!Arg->isValueDependent() &&
686 !Arg->isIntegerConstantExpr(*Result.Context)) {
687 IntegerConstantIsFirstArg =
true;
688 if (
const auto *Arg = OverloadedOperatorExpr->getArg(0)) {
689 if (!Arg->isValueDependent() &&
690 !Arg->isIntegerConstantExpr(*Result.Context))
698 Symbol = OverloadedOperatorExpr->getArg(IntegerConstantIsFirstArg ? 1 : 0);
699 OperandExpr = OverloadedOperatorExpr;
700 Opcode = BinaryOperator::getOverloadedOpcode(OverloadedOperatorExpr->getOperator());
702 if (!retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr))
705 if (!BinaryOperator::isComparisonOp(Opcode))
710 if (IntegerConstantIsFirstArg)
711 Opcode = BinaryOperator::reverseComparisonOp(Opcode);
718 if (!retrieveSymbolicExpr(Result, Id, Symbol))
721 if (Result.Nodes.getNodeAs<Expr>(SwapId))
722 Opcode = BinaryOperator::reverseComparisonOp(Opcode);
723 if (Result.Nodes.getNodeAs<Expr>(NegateId))
724 Opcode = BinaryOperator::negateComparisonOp(Opcode);
729 static bool areSidesBinaryConstExpressions(
const BinaryOperator *&BinOp,
const ASTContext *AstCtx) {
730 const auto *LhsBinOp = dyn_cast<BinaryOperator>(BinOp->getLHS());
731 const auto *RhsBinOp = dyn_cast<BinaryOperator>(BinOp->getRHS());
733 if (!LhsBinOp || !RhsBinOp)
736 auto IsIntegerConstantExpr = [AstCtx](
const Expr *
E) {
737 return !
E->isValueDependent() &&
E->isIntegerConstantExpr(*AstCtx);
740 if ((IsIntegerConstantExpr(LhsBinOp->getLHS()) ||
741 IsIntegerConstantExpr(LhsBinOp->getRHS())) &&
742 (IsIntegerConstantExpr(RhsBinOp->getLHS()) ||
743 IsIntegerConstantExpr(RhsBinOp->getRHS())))
751 static bool retrieveConstExprFromBothSides(
const BinaryOperator *&BinOp,
752 BinaryOperatorKind &MainOpcode,
753 BinaryOperatorKind &SideOpcode,
754 const Expr *&LhsConst,
755 const Expr *&RhsConst,
756 const ASTContext *AstCtx) {
757 assert(areSidesBinaryConstExpressions(BinOp, AstCtx) &&
758 "Both sides of binary operator must be constant expressions!");
760 MainOpcode = BinOp->getOpcode();
762 const auto *BinOpLhs = cast<BinaryOperator>(BinOp->getLHS());
763 const auto *BinOpRhs = cast<BinaryOperator>(BinOp->getRHS());
765 auto IsIntegerConstantExpr = [AstCtx](
const Expr *
E) {
766 return !
E->isValueDependent() &&
E->isIntegerConstantExpr(*AstCtx);
769 LhsConst = IsIntegerConstantExpr(BinOpLhs->getLHS()) ? BinOpLhs->getLHS()
770 : BinOpLhs->getRHS();
771 RhsConst = IsIntegerConstantExpr(BinOpRhs->getLHS()) ? BinOpRhs->getLHS()
772 : BinOpRhs->getRHS();
774 if (!LhsConst || !RhsConst)
777 assert(BinOpLhs->getOpcode() == BinOpRhs->getOpcode() &&
778 "Sides of the binary operator must be equivalent expressions!");
780 SideOpcode = BinOpLhs->getOpcode();
785 static bool isSameRawIdentifierToken(
const Token &T1,
const Token &T2,
786 const SourceManager &SM) {
787 if (T1.getKind() != T2.getKind())
789 if (T1.isNot(tok::raw_identifier))
791 if (T1.getLength() != T2.getLength())
793 return StringRef(SM.getCharacterData(T1.getLocation()), T1.getLength()) ==
794 StringRef(SM.getCharacterData(T2.getLocation()), T2.getLength());
797 bool isTokAtEndOfExpr(SourceRange ExprSR, Token T,
const SourceManager &SM) {
798 return SM.getExpansionLoc(ExprSR.getEnd()) == T.getLocation();
804 static bool areExprsFromDifferentMacros(
const Expr *LhsExpr,
806 const ASTContext *AstCtx) {
807 if (!LhsExpr || !RhsExpr)
809 SourceRange Lsr = LhsExpr->getSourceRange();
810 SourceRange Rsr = RhsExpr->getSourceRange();
811 if (!Lsr.getBegin().isMacroID() || !Rsr.getBegin().isMacroID())
814 const SourceManager &SM = AstCtx->getSourceManager();
815 const LangOptions &LO = AstCtx->getLangOpts();
817 std::pair<FileID, unsigned> LsrLocInfo =
818 SM.getDecomposedLoc(SM.getExpansionLoc(Lsr.getBegin()));
819 std::pair<FileID, unsigned> RsrLocInfo =
820 SM.getDecomposedLoc(SM.getExpansionLoc(Rsr.getBegin()));
821 llvm::MemoryBufferRef MB = SM.getBufferOrFake(LsrLocInfo.first);
823 const char *LTokenPos = MB.getBufferStart() + LsrLocInfo.second;
824 const char *RTokenPos = MB.getBufferStart() + RsrLocInfo.second;
825 Lexer LRawLex(SM.getLocForStartOfFile(LsrLocInfo.first), LO,
826 MB.getBufferStart(), LTokenPos, MB.getBufferEnd());
827 Lexer RRawLex(SM.getLocForStartOfFile(RsrLocInfo.first), LO,
828 MB.getBufferStart(), RTokenPos, MB.getBufferEnd());
832 LRawLex.LexFromRawLexer(LTok);
833 RRawLex.LexFromRawLexer(RTok);
834 }
while (!LTok.is(tok::eof) && !RTok.is(tok::eof) &&
835 isSameRawIdentifierToken(LTok, RTok, SM) &&
836 !isTokAtEndOfExpr(Lsr, LTok, SM) &&
837 !isTokAtEndOfExpr(Rsr, RTok, SM));
838 return (!isTokAtEndOfExpr(Lsr, LTok, SM) ||
839 !isTokAtEndOfExpr(Rsr, RTok, SM)) ||
840 !isSameRawIdentifierToken(LTok, RTok, SM);
843 static bool areExprsMacroAndNonMacro(
const Expr *&LhsExpr,
844 const Expr *&RhsExpr) {
845 if (!LhsExpr || !RhsExpr)
848 SourceLocation LhsLoc = LhsExpr->getExprLoc();
849 SourceLocation RhsLoc = RhsExpr->getExprLoc();
851 return LhsLoc.isMacroID() != RhsLoc.isMacroID();
855 void RedundantExpressionCheck::registerMatchers(MatchFinder *Finder) {
856 const auto AnyLiteralExpr = ignoringParenImpCasts(
857 anyOf(cxxBoolLiteral(), characterLiteral(), integerLiteral()));
859 const auto BannedIntegerLiteral =
860 integerLiteral(expandedByMacro(KnownBannedMacroNames));
866 anyOf(isComparisonOperator(),
867 hasAnyOperatorName(
"-",
"/",
"%",
"|",
"&",
"^",
"&&",
869 operandsAreEquivalent(),
871 unless(isInTemplateInstantiation()),
872 unless(binaryOperatorIsInMacro()),
873 unless(hasType(realFloatingPointType())),
874 unless(hasEitherOperand(hasType(realFloatingPointType()))),
875 unless(hasLHS(AnyLiteralExpr)),
876 unless(hasDescendant(BannedIntegerLiteral)))
883 binaryOperator(hasAnyOperatorName(
"|",
"&",
"||",
"&&",
"^"),
884 nestedOperandsAreEquivalent(),
886 unless(isInTemplateInstantiation()),
887 unless(binaryOperatorIsInMacro()),
889 unless(hasDescendant(BannedIntegerLiteral)))
890 .bind(
"nested-duplicates"),
896 conditionalOperator(expressionsAreEquivalent(),
898 unless(conditionalOperatorIsInMacro()),
899 unless(isInTemplateInstantiation()))
907 hasAnyOverloadedOperatorName(
"-",
"/",
"%",
"|",
"&",
"^",
908 "==",
"!=",
"<",
"<=",
">",
909 ">=",
"&&",
"||",
"="),
910 parametersAreEquivalent(),
912 unless(isMacro()), unless(isInTemplateInstantiation()))
919 hasAnyOverloadedOperatorName(
"|",
"&",
"||",
"&&",
"^"),
920 nestedParametersAreEquivalent(), argumentCountIs(2),
922 unless(isMacro()), unless(isInTemplateInstantiation()))
923 .bind(
"nested-duplicates"),
930 hasImplicitDestinationType(isInteger()),
932 hasOperatorName(
"!"),
933 hasUnaryOperand(ignoringParenImpCasts(binaryOperator(
934 hasAnyOperatorName(
"|",
"&"),
936 binaryOperator(hasAnyOperatorName(
"|",
"&")),
938 hasRHS(integerLiteral())))))
939 .bind(
"logical-bitwise-confusion")))),
946 hasOperatorName(
"&"),
947 hasOperands(ignoringParenImpCasts(binaryOperator(
948 hasOperatorName(
"<<"),
949 hasRHS(ignoringParenImpCasts(
950 integerLiteral().bind(
"shift-const"))))),
951 ignoringParenImpCasts(
952 integerLiteral().bind(
"and-const"))))
953 .bind(
"left-right-shift-confusion")),
962 const auto BinOpCstLeft = matchBinOpIntegerConstantExpr(
"lhs");
963 const auto BinOpCstRight = matchBinOpIntegerConstantExpr(
"rhs");
964 const auto CstRight = matchIntegerConstantExpr(
"rhs");
965 const auto SymRight = matchSymbolicExpr(
"rhs");
969 traverse(TK_AsIs, binaryOperator(isComparisonOperator(),
970 hasOperands(BinOpCstLeft, CstRight))
971 .bind(
"binop-const-compare-to-const")),
978 binaryOperator(isComparisonOperator(),
979 anyOf(allOf(hasLHS(BinOpCstLeft), hasRHS(SymRight)),
980 allOf(hasLHS(SymRight), hasRHS(BinOpCstLeft))))
981 .bind(
"binop-const-compare-to-sym")),
987 binaryOperator(isComparisonOperator(), hasLHS(BinOpCstLeft),
988 hasRHS(BinOpCstRight),
990 unless(operandsAreEquivalent()))
991 .bind(
"binop-const-compare-to-binop-const")),
999 const auto ComparisonLeft = matchRelationalIntegerConstantExpr(
"lhs");
1000 const auto ComparisonRight = matchRelationalIntegerConstantExpr(
"rhs");
1003 binaryOperator(hasAnyOperatorName(
"||",
"&&"),
1004 hasLHS(ComparisonLeft), hasRHS(ComparisonRight),
1006 unless(operandsAreEquivalent()))
1007 .bind(
"comparisons-of-symbol-and-const")),
1011 void RedundantExpressionCheck::checkArithmeticExpr(
1012 const MatchFinder::MatchResult &Result) {
1013 APSInt LhsValue, RhsValue;
1014 const Expr *LhsSymbol =
nullptr, *RhsSymbol =
nullptr;
1015 BinaryOperatorKind LhsOpcode, RhsOpcode;
1017 if (
const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1018 "binop-const-compare-to-sym")) {
1019 BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1020 if (!retrieveBinOpIntegerConstantExpr(Result,
"lhs", LhsOpcode, LhsSymbol,
1022 !retrieveSymbolicExpr(Result,
"rhs", RhsSymbol) ||
1023 !areEquivalentExpr(LhsSymbol, RhsSymbol))
1027 if (LhsOpcode == BO_Add || LhsOpcode == BO_Sub) {
1028 if ((LhsValue != 0 && Opcode == BO_EQ) ||
1029 (LhsValue == 0 && Opcode == BO_NE))
1030 diag(ComparisonOperator->getOperatorLoc(),
1031 "logical expression is always false");
1032 else if ((LhsValue == 0 && Opcode == BO_EQ) ||
1033 (LhsValue != 0 && Opcode == BO_NE))
1034 diag(ComparisonOperator->getOperatorLoc(),
1035 "logical expression is always true");
1037 }
else if (
const auto *ComparisonOperator =
1038 Result.Nodes.getNodeAs<BinaryOperator>(
1039 "binop-const-compare-to-binop-const")) {
1040 BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1042 if (!retrieveBinOpIntegerConstantExpr(Result,
"lhs", LhsOpcode, LhsSymbol,
1044 !retrieveBinOpIntegerConstantExpr(Result,
"rhs", RhsOpcode, RhsSymbol,
1046 !areEquivalentExpr(LhsSymbol, RhsSymbol))
1049 transformSubToCanonicalAddExpr(LhsOpcode, LhsValue);
1050 transformSubToCanonicalAddExpr(RhsOpcode, RhsValue);
1053 if (LhsOpcode == BO_Add && RhsOpcode == BO_Add) {
1054 if ((Opcode == BO_EQ && APSInt::compareValues(LhsValue, RhsValue) == 0) ||
1055 (Opcode == BO_NE && APSInt::compareValues(LhsValue, RhsValue) != 0)) {
1056 diag(ComparisonOperator->getOperatorLoc(),
1057 "logical expression is always true");
1058 }
else if ((Opcode == BO_EQ &&
1059 APSInt::compareValues(LhsValue, RhsValue) != 0) ||
1061 APSInt::compareValues(LhsValue, RhsValue) == 0)) {
1062 diag(ComparisonOperator->getOperatorLoc(),
1063 "logical expression is always false");
1070 return (Opcode == BO_And || Opcode == BO_AndAssign) && Value == 0;
1075 return (Opcode == BO_Or || Opcode == BO_OrAssign) && ~Value == 0;
1079 return ((Opcode == BO_Or || Opcode == BO_OrAssign) && Value == 0) ||
1080 ((Opcode == BO_And || Opcode == BO_AndAssign) && ~Value == 0);
1084 void RedundantExpressionCheck::checkBitwiseExpr(
1085 const MatchFinder::MatchResult &Result) {
1086 if (
const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1087 "binop-const-compare-to-const")) {
1088 BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1090 APSInt LhsValue, RhsValue;
1091 const Expr *LhsSymbol =
nullptr;
1092 BinaryOperatorKind LhsOpcode;
1093 if (!retrieveBinOpIntegerConstantExpr(Result,
"lhs", LhsOpcode, LhsSymbol,
1095 !retrieveIntegerConstantExpr(Result,
"rhs", RhsValue))
1098 uint64_t LhsConstant = LhsValue.getZExtValue();
1099 uint64_t RhsConstant = RhsValue.getZExtValue();
1100 SourceLocation
Loc = ComparisonOperator->getOperatorLoc();
1103 if (LhsOpcode == BO_And && (LhsConstant & RhsConstant) != RhsConstant) {
1104 if (Opcode == BO_EQ)
1105 diag(
Loc,
"logical expression is always false");
1106 else if (Opcode == BO_NE)
1107 diag(
Loc,
"logical expression is always true");
1111 if (LhsOpcode == BO_Or && (LhsConstant | RhsConstant) != RhsConstant) {
1112 if (Opcode == BO_EQ)
1113 diag(
Loc,
"logical expression is always false");
1114 else if (Opcode == BO_NE)
1115 diag(
Loc,
"logical expression is always true");
1117 }
else if (
const auto *IneffectiveOperator =
1118 Result.Nodes.getNodeAs<BinaryOperator>(
1119 "ineffective-bitwise")) {
1121 const Expr *Sym =
nullptr, *ConstExpr =
nullptr;
1123 if (!retrieveSymbolicExpr(Result,
"ineffective-bitwise", Sym) ||
1124 !retrieveIntegerConstantExpr(Result,
"ineffective-bitwise", Value,
1128 if((Value != 0 && ~Value != 0) || Sym->getExprLoc().isMacroID())
1131 SourceLocation
Loc = IneffectiveOperator->getOperatorLoc();
1133 BinaryOperatorKind Opcode = IneffectiveOperator->getOpcode();
1135 diag(
Loc,
"expression always evaluates to 0");
1137 SourceRange ConstExprRange(ConstExpr->getBeginLoc(),
1138 ConstExpr->getEndLoc());
1140 CharSourceRange::getTokenRange(ConstExprRange), *Result.SourceManager,
1141 Result.Context->getLangOpts());
1143 diag(
Loc,
"expression always evaluates to '%0'") << ConstExprText;
1146 SourceRange SymExprRange(Sym->getBeginLoc(), Sym->getEndLoc());
1149 CharSourceRange::getTokenRange(SymExprRange), *Result.SourceManager,
1150 Result.Context->getLangOpts());
1152 diag(
Loc,
"expression always evaluates to '%0'") << ExprText;
1157 void RedundantExpressionCheck::checkRelationalExpr(
1158 const MatchFinder::MatchResult &Result) {
1159 if (
const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1160 "comparisons-of-symbol-and-const")) {
1163 BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1165 const Expr *LhsExpr =
nullptr, *RhsExpr =
nullptr;
1166 const Expr *LhsSymbol =
nullptr, *RhsSymbol =
nullptr;
1167 const Expr *LhsConst =
nullptr, *RhsConst =
nullptr;
1168 BinaryOperatorKind LhsOpcode, RhsOpcode;
1169 APSInt LhsValue, RhsValue;
1171 if (!retrieveRelationalIntegerConstantExpr(
1172 Result,
"lhs", LhsExpr, LhsOpcode, LhsSymbol, LhsValue, LhsConst) ||
1173 !retrieveRelationalIntegerConstantExpr(
1174 Result,
"rhs", RhsExpr, RhsOpcode, RhsSymbol, RhsValue, RhsConst) ||
1175 !areEquivalentExpr(LhsSymbol, RhsSymbol))
1179 if (APSInt::compareValues(LhsValue, RhsValue) > 0) {
1180 std::swap(LhsExpr, RhsExpr);
1181 std::swap(LhsValue, RhsValue);
1182 std::swap(LhsSymbol, RhsSymbol);
1183 std::swap(LhsOpcode, RhsOpcode);
1187 if (areExprsFromDifferentMacros(LhsConst, RhsConst, Result.Context) ||
1188 areExprsMacroAndNonMacro(LhsConst, RhsConst))
1191 if ((Opcode == BO_LAnd || Opcode == BO_LOr) &&
1192 areEquivalentRanges(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1193 diag(ComparisonOperator->getOperatorLoc(),
1194 "equivalent expression on both sides of logical operator");
1198 if (Opcode == BO_LAnd) {
1199 if (areExclusiveRanges(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1200 diag(ComparisonOperator->getOperatorLoc(),
1201 "logical expression is always false");
1202 }
else if (rangeSubsumesRange(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1203 diag(LhsExpr->getExprLoc(),
"expression is redundant");
1204 }
else if (rangeSubsumesRange(RhsOpcode, RhsValue, LhsOpcode, LhsValue)) {
1205 diag(RhsExpr->getExprLoc(),
"expression is redundant");
1209 if (Opcode == BO_LOr) {
1210 if (rangesFullyCoverDomain(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1211 diag(ComparisonOperator->getOperatorLoc(),
1212 "logical expression is always true");
1213 }
else if (rangeSubsumesRange(LhsOpcode, LhsValue, RhsOpcode, RhsValue)) {
1214 diag(RhsExpr->getExprLoc(),
"expression is redundant");
1215 }
else if (rangeSubsumesRange(RhsOpcode, RhsValue, LhsOpcode, LhsValue)) {
1216 diag(LhsExpr->getExprLoc(),
"expression is redundant");
1223 if (
const auto *BinOp = Result.Nodes.getNodeAs<BinaryOperator>(
"binary")) {
1226 if (areSidesBinaryConstExpressions(BinOp, Result.Context)) {
1227 const Expr *LhsConst =
nullptr, *RhsConst =
nullptr;
1228 BinaryOperatorKind MainOpcode, SideOpcode;
1230 if (!retrieveConstExprFromBothSides(BinOp, MainOpcode, SideOpcode,
1231 LhsConst, RhsConst, Result.Context))
1234 if (areExprsFromDifferentMacros(LhsConst, RhsConst, Result.Context) ||
1235 areExprsMacroAndNonMacro(LhsConst, RhsConst))
1239 diag(BinOp->getOperatorLoc(),
"both sides of operator are equivalent");
1242 if (
const auto *CondOp =
1243 Result.Nodes.getNodeAs<ConditionalOperator>(
"cond")) {
1244 const Expr *TrueExpr = CondOp->getTrueExpr();
1245 const Expr *FalseExpr = CondOp->getFalseExpr();
1247 if (areExprsFromDifferentMacros(TrueExpr, FalseExpr, Result.Context) ||
1248 areExprsMacroAndNonMacro(TrueExpr, FalseExpr))
1250 diag(CondOp->getColonLoc(),
1251 "'true' and 'false' expressions are equivalent");
1254 if (
const auto *Call = Result.Nodes.getNodeAs<CXXOperatorCallExpr>(
"call")) {
1255 if (canOverloadedOperatorArgsBeModified(Call,
true))
1258 diag(Call->getOperatorLoc(),
1259 "both sides of overloaded operator are equivalent");
1262 if (
const auto *Op = Result.Nodes.getNodeAs<Expr>(
"nested-duplicates")) {
1263 const auto *Call = dyn_cast<CXXOperatorCallExpr>(Op);
1264 if (Call && canOverloadedOperatorArgsBeModified(Call,
true))
1268 Call ?
"overloaded operator has equivalent nested operands"
1269 :
"operator has equivalent nested operands";
1271 const auto Diag = diag(Op->getExprLoc(),
Message);
1272 for (
const auto &KeyValue : Result.Nodes.getMap()) {
1273 if (StringRef(KeyValue.first).startswith(
"duplicate"))
1274 Diag << KeyValue.second.getSourceRange();
1278 if (
const auto *NegateOperator =
1279 Result.Nodes.getNodeAs<UnaryOperator>(
"logical-bitwise-confusion")) {
1280 SourceLocation OperatorLoc = NegateOperator->getOperatorLoc();
1284 "ineffective logical negation operator used; did you mean '~'?");
1285 SourceLocation LogicalNotLocation = OperatorLoc.getLocWithOffset(1);
1287 if (!LogicalNotLocation.isMacroID())
1288 Diag << FixItHint::CreateReplacement(
1289 CharSourceRange::getCharRange(OperatorLoc, LogicalNotLocation),
"~");
1292 if (
const auto *BinaryAndExpr = Result.Nodes.getNodeAs<BinaryOperator>(
1293 "left-right-shift-confusion")) {
1294 const auto *ShiftingConst = Result.Nodes.getNodeAs<Expr>(
"shift-const");
1295 assert(ShiftingConst &&
"Expr* 'ShiftingConst' is nullptr!");
1296 Optional<llvm::APSInt> ShiftingValue =
1297 ShiftingConst->getIntegerConstantExpr(*Result.Context);
1302 const auto *AndConst = Result.Nodes.getNodeAs<Expr>(
"and-const");
1303 assert(AndConst &&
"Expr* 'AndCont' is nullptr!");
1304 Optional<llvm::APSInt> AndValue =
1305 AndConst->getIntegerConstantExpr(*Result.Context);
1312 if (AndValue->getActiveBits() > *ShiftingValue)
1315 auto Diag = diag(BinaryAndExpr->getOperatorLoc(),
1316 "ineffective bitwise and operation");
1324 checkArithmeticExpr(Result);
1332 checkBitwiseExpr(Result);
1340 checkRelationalExpr(Result);