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