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     if (cast<BinaryOperator>(Left)->isAssignmentOp())
138       return false;
139     return cast<BinaryOperator>(Left)->getOpcode() ==
140            cast<BinaryOperator>(Right)->getOpcode();
141   case Stmt::UnaryExprOrTypeTraitExprClass:
142     const auto *LeftUnaryExpr =
143         cast<UnaryExprOrTypeTraitExpr>(Left);
144     const auto *RightUnaryExpr =
145         cast<UnaryExprOrTypeTraitExpr>(Right);
146     if (LeftUnaryExpr->isArgumentType() && RightUnaryExpr->isArgumentType())
147       return LeftUnaryExpr->getArgumentType() ==
148              RightUnaryExpr->getArgumentType();
149     if (!LeftUnaryExpr->isArgumentType() && !RightUnaryExpr->isArgumentType())
150       return areEquivalentExpr(LeftUnaryExpr->getArgumentExpr(),
151                                RightUnaryExpr->getArgumentExpr());
152 
153     return false;
154   }
155 }
156 
157 // For a given expression 'x', returns whether the ranges covered by the
158 // relational operators are equivalent (i.e.  x <= 4 is equivalent to x < 5).
areEquivalentRanges(BinaryOperatorKind OpcodeLHS,const APSInt & ValueLHS,BinaryOperatorKind OpcodeRHS,const APSInt & ValueRHS)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");
165   // Handle the case where constants are the same: x <= 4  <==>  x <= 4.
166   if (APSInt::compareValues(ValueLHS, ValueRHS) == 0)
167     return OpcodeLHS == OpcodeRHS;
168 
169   // Handle the case where constants are off by one: x <= 4  <==>  x < 5.
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;
175 }
176 
177 // For a given expression 'x', returns whether the ranges covered by the
178 // relational operators are fully disjoint (i.e. x < 4  and  x > 7).
areExclusiveRanges(BinaryOperatorKind OpcodeLHS,const APSInt & ValueLHS,BinaryOperatorKind OpcodeRHS,const APSInt & ValueRHS)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");
185 
186   // Handle cases where the constants are the same.
187   if (APSInt::compareValues(ValueLHS, ValueRHS) == 0) {
188     switch (OpcodeLHS) {
189     case BO_EQ:
190       return OpcodeRHS == BO_NE || OpcodeRHS == BO_GT || OpcodeRHS == BO_LT;
191     case BO_NE:
192       return OpcodeRHS == BO_EQ;
193     case BO_LE:
194       return OpcodeRHS == BO_GT;
195     case BO_GE:
196       return OpcodeRHS == BO_LT;
197     case BO_LT:
198       return OpcodeRHS == BO_EQ || OpcodeRHS == BO_GT || OpcodeRHS == BO_GE;
199     case BO_GT:
200       return OpcodeRHS == BO_EQ || OpcodeRHS == BO_LT || OpcodeRHS == BO_LE;
201     default:
202       return false;
203     }
204   }
205 
206   // Handle cases where the constants are different.
207   if ((OpcodeLHS == BO_EQ || OpcodeLHS == BO_LT || OpcodeLHS == BO_LE) &&
208       (OpcodeRHS == BO_EQ || OpcodeRHS == BO_GT || OpcodeRHS == BO_GE))
209     return true;
210 
211   // Handle the case where constants are off by one: x > 5 && x < 6.
212   APSInt ValueLhsPlus1;
213   if (OpcodeLHS == BO_GT && OpcodeRHS == BO_LT &&
214       incrementWithoutOverflow(ValueLHS, ValueLhsPlus1) &&
215       APSInt::compareValues(ValueLhsPlus1, ValueRHS) == 0)
216     return true;
217 
218   return false;
219 }
220 
221 // Returns whether the ranges covered by the union of both relational
222 // expressions cover the whole domain (i.e. x < 10  and  x > 0).
rangesFullyCoverDomain(BinaryOperatorKind OpcodeLHS,const APSInt & ValueLHS,BinaryOperatorKind OpcodeRHS,const APSInt & ValueRHS)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");
229 
230   // Handle cases where the constants are the same:  x < 5 || x >= 5.
231   if (APSInt::compareValues(ValueLHS, ValueRHS) == 0) {
232     switch (OpcodeLHS) {
233     case BO_EQ:
234       return OpcodeRHS == BO_NE;
235     case BO_NE:
236       return OpcodeRHS == BO_EQ;
237     case BO_LE:
238       return OpcodeRHS == BO_GT || OpcodeRHS == BO_GE;
239     case BO_LT:
240       return OpcodeRHS == BO_GE;
241     case BO_GE:
242       return OpcodeRHS == BO_LT || OpcodeRHS == BO_LE;
243     case BO_GT:
244       return OpcodeRHS == BO_LE;
245     default:
246       return false;
247     }
248   }
249 
250   // Handle the case where constants are off by one: x <= 4 || x >= 5.
251   APSInt ValueLhsPlus1;
252   if (OpcodeLHS == BO_LE && OpcodeRHS == BO_GE &&
253       incrementWithoutOverflow(ValueLHS, ValueLhsPlus1) &&
254       APSInt::compareValues(ValueLhsPlus1, ValueRHS) == 0)
255     return true;
256 
257   // Handle cases where the constants are different: x > 4 || x <= 7.
258   if ((OpcodeLHS == BO_GT || OpcodeLHS == BO_GE) &&
259       (OpcodeRHS == BO_LT || OpcodeRHS == BO_LE))
260     return true;
261 
262   // Handle cases where constants are different but both ops are !=, like:
263   // x != 5 || x != 10
264   if (OpcodeLHS == BO_NE && OpcodeRHS == BO_NE)
265     return true;
266 
267   return false;
268 }
269 
rangeSubsumesRange(BinaryOperatorKind OpcodeLHS,const APSInt & ValueLHS,BinaryOperatorKind OpcodeRHS,const APSInt & ValueRHS)270 static bool rangeSubsumesRange(BinaryOperatorKind OpcodeLHS,
271                                const APSInt &ValueLHS,
272                                BinaryOperatorKind OpcodeRHS,
273                                const APSInt &ValueRHS) {
274   int Comparison = APSInt::compareValues(ValueLHS, ValueRHS);
275   switch (OpcodeLHS) {
276   case BO_EQ:
277     return OpcodeRHS == BO_EQ && Comparison == 0;
278   case BO_NE:
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);
285 
286   case BO_LT:
287     return ((OpcodeRHS == BO_LT && Comparison >= 0) ||
288             (OpcodeRHS == BO_LE && Comparison > 0) ||
289             (OpcodeRHS == BO_EQ && Comparison > 0));
290   case BO_GT:
291     return ((OpcodeRHS == BO_GT && Comparison <= 0) ||
292             (OpcodeRHS == BO_GE && Comparison < 0) ||
293             (OpcodeRHS == BO_EQ && Comparison < 0));
294   case BO_LE:
295     return (OpcodeRHS == BO_LT || OpcodeRHS == BO_LE || OpcodeRHS == BO_EQ) &&
296            Comparison >= 0;
297   case BO_GE:
298     return (OpcodeRHS == BO_GT || OpcodeRHS == BO_GE || OpcodeRHS == BO_EQ) &&
299            Comparison <= 0;
300   default:
301     return false;
302   }
303 }
304 
transformSubToCanonicalAddExpr(BinaryOperatorKind & Opcode,APSInt & Value)305 static void transformSubToCanonicalAddExpr(BinaryOperatorKind &Opcode,
306                                            APSInt &Value) {
307   if (Opcode == BO_Sub) {
308     Opcode = BO_Add;
309     Value = -Value;
310   }
311 }
312 
313 // to use in the template below
getOp(const BinaryOperator * Op)314 static OverloadedOperatorKind getOp(const BinaryOperator *Op) {
315   return BinaryOperator::getOverloadedOperator(Op->getOpcode());
316 }
317 
getOp(const CXXOperatorCallExpr * Op)318 static OverloadedOperatorKind getOp(const CXXOperatorCallExpr *Op) {
319   if (Op->getNumArgs() != 2)
320     return OO_None;
321   return Op->getOperator();
322 }
323 
324 static std::pair<const Expr *, const Expr *>
getOperands(const BinaryOperator * Op)325 getOperands(const BinaryOperator *Op) {
326   return {Op->getLHS()->IgnoreParenImpCasts(),
327           Op->getRHS()->IgnoreParenImpCasts()};
328 }
329 
330 static std::pair<const Expr *, const Expr *>
getOperands(const CXXOperatorCallExpr * Op)331 getOperands(const CXXOperatorCallExpr *Op) {
332   return {Op->getArg(0)->IgnoreParenImpCasts(),
333           Op->getArg(1)->IgnoreParenImpCasts()};
334 }
335 
336 template <typename TExpr>
checkOpKind(const Expr * TheExpr,OverloadedOperatorKind OpKind)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)
341     return AsTExpr;
342 
343   return nullptr;
344 }
345 
346 // returns true if a subexpression has two directly equivalent operands and
347 // is already handled by operands/parametersAreEquivalent
348 template <typename TExpr, unsigned N>
collectOperands(const Expr * Part,SmallVector<const Expr *,N> & AllOperands,OverloadedOperatorKind OpKind)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))
355       return true;
356     return collectOperands<TExpr>(Operands.first, AllOperands, OpKind) ||
357            collectOperands<TExpr>(Operands.second, AllOperands, OpKind);
358   }
359 
360   AllOperands.push_back(Part);
361   return false;
362 }
363 
364 template <typename TExpr>
hasSameOperatorParent(const Expr * TheExpr,OverloadedOperatorKind OpKind,ASTContext & Context)365 static bool hasSameOperatorParent(const Expr *TheExpr,
366                                   OverloadedOperatorKind OpKind,
367                                   ASTContext &Context) {
368   // IgnoreParenImpCasts logic in reverse: skip surrounding uninteresting nodes
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) ||
373                   isa<FullExpr>(Parent) ||
374                   isa<MaterializeTemporaryExpr>(Parent);
375       if (Skip && hasSameOperatorParent<TExpr>(Parent, OpKind, Context))
376         return true;
377       if (checkOpKind<TExpr>(Parent, OpKind))
378         return true;
379     }
380   }
381 
382   return false;
383 }
384 
385 template <typename TExpr>
386 static bool
markDuplicateOperands(const TExpr * TheExpr,ast_matchers::internal::BoundNodesTreeBuilder * Builder,ASTContext & Context)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)
392     return false;
393   // if there are no nested operators of the same kind, it's handled by
394   // operands/parametersAreEquivalent
395   const std::pair<const Expr *, const Expr *> Operands = getOperands(TheExpr);
396   if (!(checkOpKind<TExpr>(Operands.first, OpKind) ||
397         checkOpKind<TExpr>(Operands.second, OpKind)))
398     return false;
399 
400   // if parent is the same kind of operator, it's handled by a previous call to
401   // markDuplicateOperands
402   if (hasSameOperatorParent<TExpr>(TheExpr, OpKind, Context))
403     return false;
404 
405   SmallVector<const Expr *, 4> AllOperands;
406   if (collectOperands<TExpr>(Operands.first, AllOperands, OpKind))
407     return false;
408   if (collectOperands<TExpr>(Operands.second, AllOperands, OpKind))
409     return false;
410   size_t NumOperands = AllOperands.size();
411   llvm::SmallBitVector Duplicates(NumOperands);
412   for (size_t I = 0; I < NumOperands; I++) {
413     if (Duplicates[I])
414       continue;
415     bool FoundDuplicates = false;
416 
417     for (size_t J = I + 1; J < NumOperands; J++) {
418       if (AllOperands[J]->HasSideEffects(Context))
419         break;
420 
421       if (areEquivalentExpr(AllOperands[I], AllOperands[J])) {
422         FoundDuplicates = true;
423         Duplicates.set(J);
424         Builder->setBinding(SmallString<11>(llvm::formatv("duplicate{0}", J)),
425                             DynTypedNode::create(*AllOperands[J]));
426       }
427     }
428 
429     if (FoundDuplicates)
430       Builder->setBinding(SmallString<11>(llvm::formatv("duplicate{0}", I)),
431                           DynTypedNode::create(*AllOperands[I]));
432   }
433 
434   return Duplicates.any();
435 }
436 
AST_MATCHER(Expr,isIntegerConstantExpr)437 AST_MATCHER(Expr, isIntegerConstantExpr) {
438   if (Node.isInstantiationDependent())
439     return false;
440   return Node.isIntegerConstantExpr(Finder->getASTContext());
441 }
442 
AST_MATCHER(BinaryOperator,operandsAreEquivalent)443 AST_MATCHER(BinaryOperator, operandsAreEquivalent) {
444   return areEquivalentExpr(Node.getLHS(), Node.getRHS());
445 }
446 
AST_MATCHER(BinaryOperator,nestedOperandsAreEquivalent)447 AST_MATCHER(BinaryOperator, nestedOperandsAreEquivalent) {
448   return markDuplicateOperands(&Node, Builder, Finder->getASTContext());
449 }
450 
AST_MATCHER(ConditionalOperator,expressionsAreEquivalent)451 AST_MATCHER(ConditionalOperator, expressionsAreEquivalent) {
452   return areEquivalentExpr(Node.getTrueExpr(), Node.getFalseExpr());
453 }
454 
AST_MATCHER(CallExpr,parametersAreEquivalent)455 AST_MATCHER(CallExpr, parametersAreEquivalent) {
456   return Node.getNumArgs() == 2 &&
457          areEquivalentExpr(Node.getArg(0), Node.getArg(1));
458 }
459 
AST_MATCHER(CXXOperatorCallExpr,nestedParametersAreEquivalent)460 AST_MATCHER(CXXOperatorCallExpr, nestedParametersAreEquivalent) {
461   return markDuplicateOperands(&Node, Builder, Finder->getASTContext());
462 }
463 
AST_MATCHER(BinaryOperator,binaryOperatorIsInMacro)464 AST_MATCHER(BinaryOperator, binaryOperatorIsInMacro) {
465   return Node.getOperatorLoc().isMacroID();
466 }
467 
AST_MATCHER(ConditionalOperator,conditionalOperatorIsInMacro)468 AST_MATCHER(ConditionalOperator, conditionalOperatorIsInMacro) {
469   return Node.getQuestionLoc().isMacroID() || Node.getColonLoc().isMacroID();
470 }
471 
AST_MATCHER(Expr,isMacro)472 AST_MATCHER(Expr, isMacro) { return Node.getExprLoc().isMacroID(); }
473 
AST_MATCHER_P(Expr,expandedByMacro,ArrayRef<llvm::StringLiteral>,Names)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))
481       return true;
482     Loc = SM.getImmediateMacroCallerLoc(Loc);
483   }
484   return false;
485 }
486 
487 // Returns a matcher for integer constant expressions.
488 static ast_matchers::internal::Matcher<Expr>
matchIntegerConstantExpr(StringRef Id)489 matchIntegerConstantExpr(StringRef Id) {
490   std::string CstId = (Id + "-const").str();
491   return expr(isIntegerConstantExpr()).bind(CstId);
492 }
493 
494 // Retrieves the integer expression matched by 'matchIntegerConstantExpr' with
495 // name 'Id' and stores it into 'ConstExpr', the value of the expression is
496 // stored into `Value`.
retrieveIntegerConstantExpr(const MatchFinder::MatchResult & Result,StringRef Id,APSInt & Value,const Expr * & ConstExpr)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);
502   if (!ConstExpr)
503     return false;
504   Optional<llvm::APSInt> R = ConstExpr->getIntegerConstantExpr(*Result.Context);
505   if (!R)
506     return false;
507   Value = *R;
508   return true;
509 }
510 
511 // Overloaded `retrieveIntegerConstantExpr` for compatibility.
retrieveIntegerConstantExpr(const MatchFinder::MatchResult & Result,StringRef Id,APSInt & Value)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);
516 }
517 
518 // Returns a matcher for symbolic expressions (matches every expression except
519 // ingeter constant expressions).
matchSymbolicExpr(StringRef Id)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));
524 }
525 
526 // Retrieves the expression matched by 'matchSymbolicExpr' with name 'Id' and
527 // stores it into 'SymExpr'.
retrieveSymbolicExpr(const MatchFinder::MatchResult & Result,StringRef Id,const Expr * & SymExpr)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)) {
532     SymExpr = Node;
533     return true;
534   }
535   return false;
536 }
537 
538 // Match a binary operator between a symbolic expression and an integer constant
539 // expression.
540 static ast_matchers::internal::Matcher<Expr>
matchBinOpIntegerConstantExpr(StringRef Id)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)))))
549           .bind(Id);
550   return ignoringParenImpCasts(BinOpCstExpr);
551 }
552 
553 // Retrieves sub-expressions matched by 'matchBinOpIntegerConstantExpr' with
554 // name 'Id'.
555 static bool
retrieveBinOpIntegerConstantExpr(const MatchFinder::MatchResult & Result,StringRef Id,BinaryOperatorKind & Opcode,const Expr * & Symbol,APSInt & Value)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);
563   }
564   return false;
565 }
566 
567 // Matches relational expressions: 'Expr <op> k' (i.e. x < 2, x != 3, 12 <= x).
568 static ast_matchers::internal::Matcher<Expr>
matchRelationalIntegerConstantExpr(StringRef Id)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();
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           anyOf(hasLHS(ignoringParenImpCasts(integerLiteral().bind(ConstId))),
608                 hasRHS(ignoringParenImpCasts(integerLiteral().bind(ConstId)))))
609           .bind(OverloadId);
610 
611   return anyOf(RelationalExpr, CastExpr, NegateRelationalExpr,
612                NegateNegateRelationalExpr, OverloadedOperatorExpr);
613 }
614 
615 // Checks whether a function param is non constant reference type, and may
616 // be modified in the function.
isNonConstReferenceType(QualType ParamType)617 static bool isNonConstReferenceType(QualType ParamType) {
618   return ParamType->isReferenceType() &&
619          !ParamType.getNonReferenceType().isConstQualified();
620 }
621 
622 // Checks whether the arguments of an overloaded operator can be modified in the
623 // function.
624 // For operators that take an instance and a constant as arguments, only the
625 // first argument (the instance) needs to be checked, since the constant itself
626 // is a temporary expression. Whether the second parameter is checked is
627 // controlled by the parameter `ParamsToCheckCount`.
628 static bool
canOverloadedOperatorArgsBeModified(const CXXOperatorCallExpr * OperatorCall,bool CheckSecondParam)629 canOverloadedOperatorArgsBeModified(const CXXOperatorCallExpr *OperatorCall,
630                                     bool CheckSecondParam) {
631   const auto *OperatorDecl =
632       dyn_cast_or_null<FunctionDecl>(OperatorCall->getCalleeDecl());
633   // if we can't find the declaration, conservatively assume it can modify
634   // arguments
635   if (!OperatorDecl)
636     return true;
637 
638   unsigned ParamCount = OperatorDecl->getNumParams();
639 
640   // Overloaded operators declared inside a class have only one param.
641   // These functions must be declared const in order to not be able to modify
642   // the instance of the class they are called through.
643   if (ParamCount == 1 &&
644       !OperatorDecl->getType()->castAs<FunctionType>()->isConst())
645     return true;
646 
647   if (isNonConstReferenceType(OperatorDecl->getParamDecl(0)->getType()))
648     return true;
649 
650   return CheckSecondParam && ParamCount == 2 &&
651          isNonConstReferenceType(OperatorDecl->getParamDecl(1)->getType());
652 }
653 
654 // Retrieves sub-expressions matched by 'matchRelationalIntegerConstantExpr'
655 // with name 'Id'.
retrieveRelationalIntegerConstantExpr(const MatchFinder::MatchResult & Result,StringRef Id,const Expr * & OperandExpr,BinaryOperatorKind & Opcode,const Expr * & Symbol,APSInt & Value,const Expr * & ConstExpr)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();
664 
665   if (const auto *Bin = Result.Nodes.getNodeAs<BinaryOperator>(Id)) {
666     // Operand received with explicit comparator.
667     Opcode = Bin->getOpcode();
668     OperandExpr = Bin;
669 
670     if (!retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr))
671       return false;
672   } else if (const auto *Cast = Result.Nodes.getNodeAs<CastExpr>(CastId)) {
673     // Operand received with implicit comparator (cast).
674     Opcode = BO_NE;
675     OperandExpr = Cast;
676     Value = APSInt(32, false);
677   } else if (const auto *OverloadedOperatorExpr =
678                  Result.Nodes.getNodeAs<CXXOperatorCallExpr>(OverloadId)) {
679     if (canOverloadedOperatorArgsBeModified(OverloadedOperatorExpr, false))
680       return false;
681 
682     bool IntegerConstantIsFirstArg = false;
683 
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))
691             return false;
692         } else
693           return false;
694       }
695     } else
696       return false;
697 
698     Symbol = OverloadedOperatorExpr->getArg(IntegerConstantIsFirstArg ? 1 : 0);
699     OperandExpr = OverloadedOperatorExpr;
700     Opcode = BinaryOperator::getOverloadedOpcode(OverloadedOperatorExpr->getOperator());
701 
702     if (!retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr))
703       return false;
704 
705     if (!BinaryOperator::isComparisonOp(Opcode))
706       return false;
707 
708     // The call site of this function expects the constant on the RHS,
709     // so change the opcode accordingly.
710     if (IntegerConstantIsFirstArg)
711       Opcode = BinaryOperator::reverseComparisonOp(Opcode);
712 
713     return true;
714   } else {
715     return false;
716   }
717 
718   if (!retrieveSymbolicExpr(Result, Id, Symbol))
719     return false;
720 
721   if (Result.Nodes.getNodeAs<Expr>(SwapId))
722     Opcode = BinaryOperator::reverseComparisonOp(Opcode);
723   if (Result.Nodes.getNodeAs<Expr>(NegateId))
724     Opcode = BinaryOperator::negateComparisonOp(Opcode);
725   return true;
726 }
727 
728 // Checks for expressions like (X == 4) && (Y != 9)
areSidesBinaryConstExpressions(const BinaryOperator * & BinOp,const ASTContext * AstCtx)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());
732 
733   if (!LhsBinOp || !RhsBinOp)
734     return false;
735 
736   auto IsIntegerConstantExpr = [AstCtx](const Expr *E) {
737     return !E->isValueDependent() && E->isIntegerConstantExpr(*AstCtx);
738   };
739 
740   if ((IsIntegerConstantExpr(LhsBinOp->getLHS()) ||
741        IsIntegerConstantExpr(LhsBinOp->getRHS())) &&
742       (IsIntegerConstantExpr(RhsBinOp->getLHS()) ||
743        IsIntegerConstantExpr(RhsBinOp->getRHS())))
744     return true;
745   return false;
746 }
747 
748 // Retrieves integer constant subexpressions from binary operator expressions
749 // that have two equivalent sides.
750 // 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)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!");
759 
760   MainOpcode = BinOp->getOpcode();
761 
762   const auto *BinOpLhs = cast<BinaryOperator>(BinOp->getLHS());
763   const auto *BinOpRhs = cast<BinaryOperator>(BinOp->getRHS());
764 
765   auto IsIntegerConstantExpr = [AstCtx](const Expr *E) {
766     return !E->isValueDependent() && E->isIntegerConstantExpr(*AstCtx);
767   };
768 
769   LhsConst = IsIntegerConstantExpr(BinOpLhs->getLHS()) ? BinOpLhs->getLHS()
770                                                        : BinOpLhs->getRHS();
771   RhsConst = IsIntegerConstantExpr(BinOpRhs->getLHS()) ? BinOpRhs->getLHS()
772                                                        : BinOpRhs->getRHS();
773 
774   if (!LhsConst || !RhsConst)
775     return false;
776 
777   assert(BinOpLhs->getOpcode() == BinOpRhs->getOpcode() &&
778          "Sides of the binary operator must be equivalent expressions!");
779 
780   SideOpcode = BinOpLhs->getOpcode();
781 
782   return true;
783 }
784 
isSameRawIdentifierToken(const Token & T1,const Token & T2,const SourceManager & SM)785 static bool isSameRawIdentifierToken(const Token &T1, const Token &T2,
786                         const SourceManager &SM) {
787   if (T1.getKind() != T2.getKind())
788     return false;
789   if (T1.isNot(tok::raw_identifier))
790     return true;
791   if (T1.getLength() != T2.getLength())
792     return false;
793   return StringRef(SM.getCharacterData(T1.getLocation()), T1.getLength()) ==
794          StringRef(SM.getCharacterData(T2.getLocation()), T2.getLength());
795 }
796 
isTokAtEndOfExpr(SourceRange ExprSR,Token T,const SourceManager & SM)797 bool isTokAtEndOfExpr(SourceRange ExprSR, Token T, const SourceManager &SM) {
798   return SM.getExpansionLoc(ExprSR.getEnd()) == T.getLocation();
799 }
800 
801 /// Returns true if both LhsExpr and RhsExpr are
802 /// macro expressions and they are expanded
803 /// from different macros.
areExprsFromDifferentMacros(const Expr * LhsExpr,const Expr * RhsExpr,const ASTContext * AstCtx)804 static bool areExprsFromDifferentMacros(const Expr *LhsExpr,
805                                         const Expr *RhsExpr,
806                                         const ASTContext *AstCtx) {
807   if (!LhsExpr || !RhsExpr)
808     return false;
809   SourceRange Lsr = LhsExpr->getSourceRange();
810   SourceRange Rsr = RhsExpr->getSourceRange();
811   if (!Lsr.getBegin().isMacroID() || !Rsr.getBegin().isMacroID())
812     return false;
813 
814   const SourceManager &SM = AstCtx->getSourceManager();
815   const LangOptions &LO = AstCtx->getLangOpts();
816 
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);
822 
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());
829 
830   Token LTok, RTok;
831   do { // Compare the expressions token-by-token.
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);
841 }
842 
areExprsMacroAndNonMacro(const Expr * & LhsExpr,const Expr * & RhsExpr)843 static bool areExprsMacroAndNonMacro(const Expr *&LhsExpr,
844                                      const Expr *&RhsExpr) {
845   if (!LhsExpr || !RhsExpr)
846     return false;
847 
848   SourceLocation LhsLoc = LhsExpr->getExprLoc();
849   SourceLocation RhsLoc = RhsExpr->getExprLoc();
850 
851   return LhsLoc.isMacroID() != RhsLoc.isMacroID();
852 }
853 } // namespace
854 
registerMatchers(MatchFinder * Finder)855 void RedundantExpressionCheck::registerMatchers(MatchFinder *Finder) {
856   const auto AnyLiteralExpr = ignoringParenImpCasts(
857       anyOf(cxxBoolLiteral(), characterLiteral(), integerLiteral()));
858 
859   const auto BannedIntegerLiteral =
860       integerLiteral(expandedByMacro(KnownBannedMacroNames));
861 
862   // Binary with equivalent operands, like (X != 2 && X != 2).
863   Finder->addMatcher(
864       traverse(TK_AsIs,
865                binaryOperator(
866                    anyOf(isComparisonOperator(),
867                          hasAnyOperatorName("-", "/", "%", "|", "&", "^", "&&",
868                                             "||", "=")),
869                    operandsAreEquivalent(),
870                    // Filter noisy false positives.
871                    unless(isInTemplateInstantiation()),
872                    unless(binaryOperatorIsInMacro()),
873                    unless(hasType(realFloatingPointType())),
874                    unless(hasEitherOperand(hasType(realFloatingPointType()))),
875                    unless(hasLHS(AnyLiteralExpr)),
876                    unless(hasDescendant(BannedIntegerLiteral)))
877                    .bind("binary")),
878       this);
879 
880   // Logical or bitwise operator with equivalent nested operands, like (X && Y
881   // && X) or (X && (Y && X))
882   Finder->addMatcher(
883       binaryOperator(hasAnyOperatorName("|", "&", "||", "&&", "^"),
884                      nestedOperandsAreEquivalent(),
885                      // Filter noisy false positives.
886                      unless(isInTemplateInstantiation()),
887                      unless(binaryOperatorIsInMacro()),
888                      // TODO: if the banned macros are themselves duplicated
889                      unless(hasDescendant(BannedIntegerLiteral)))
890           .bind("nested-duplicates"),
891       this);
892 
893   // Conditional (ternary) operator with equivalent operands, like (Y ? X : X).
894   Finder->addMatcher(
895       traverse(TK_AsIs,
896                conditionalOperator(expressionsAreEquivalent(),
897                                    // Filter noisy false positives.
898                                    unless(conditionalOperatorIsInMacro()),
899                                    unless(isInTemplateInstantiation()))
900                    .bind("cond")),
901       this);
902 
903   // Overloaded operators with equivalent operands.
904   Finder->addMatcher(
905       traverse(TK_AsIs,
906                cxxOperatorCallExpr(
907                    hasAnyOverloadedOperatorName("-", "/", "%", "|", "&", "^",
908                                                 "==", "!=", "<", "<=", ">",
909                                                 ">=", "&&", "||", "="),
910                    parametersAreEquivalent(),
911                    // Filter noisy false positives.
912                    unless(isMacro()), unless(isInTemplateInstantiation()))
913                    .bind("call")),
914       this);
915 
916   // Overloaded operators with equivalent operands.
917   Finder->addMatcher(
918       cxxOperatorCallExpr(
919           hasAnyOverloadedOperatorName("|", "&", "||", "&&", "^"),
920           nestedParametersAreEquivalent(), argumentCountIs(2),
921           // Filter noisy false positives.
922           unless(isMacro()), unless(isInTemplateInstantiation()))
923           .bind("nested-duplicates"),
924       this);
925 
926   // Match expressions like: !(1 | 2 | 3)
927   Finder->addMatcher(
928       traverse(TK_AsIs,
929                implicitCastExpr(
930                    hasImplicitDestinationType(isInteger()),
931                    has(unaryOperator(
932                            hasOperatorName("!"),
933                            hasUnaryOperand(ignoringParenImpCasts(binaryOperator(
934                                hasAnyOperatorName("|", "&"),
935                                hasLHS(anyOf(
936                                    binaryOperator(hasAnyOperatorName("|", "&")),
937                                    integerLiteral())),
938                                hasRHS(integerLiteral())))))
939                            .bind("logical-bitwise-confusion")))),
940       this);
941 
942   // Match expressions like: (X << 8) & 0xFF
943   Finder->addMatcher(
944       traverse(TK_AsIs,
945                binaryOperator(
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")),
954       this);
955 
956   // Match common expressions and apply more checks to find redundant
957   // sub-expressions.
958   //   a) Expr <op> K1 == K2
959   //   b) Expr <op> K1 == Expr
960   //   c) Expr <op> K1 == Expr <op> K2
961   // see: 'checkArithmeticExpr' and 'checkBitwiseExpr'
962   const auto BinOpCstLeft = matchBinOpIntegerConstantExpr("lhs");
963   const auto BinOpCstRight = matchBinOpIntegerConstantExpr("rhs");
964   const auto CstRight = matchIntegerConstantExpr("rhs");
965   const auto SymRight = matchSymbolicExpr("rhs");
966 
967   // Match expressions like: x <op> 0xFF == 0xF00.
968   Finder->addMatcher(
969       traverse(TK_AsIs, binaryOperator(isComparisonOperator(),
970                                        hasOperands(BinOpCstLeft, CstRight))
971                             .bind("binop-const-compare-to-const")),
972       this);
973 
974   // Match expressions like: x <op> 0xFF == x.
975   Finder->addMatcher(
976       traverse(
977           TK_AsIs,
978           binaryOperator(isComparisonOperator(),
979                          anyOf(allOf(hasLHS(BinOpCstLeft), hasRHS(SymRight)),
980                                allOf(hasLHS(SymRight), hasRHS(BinOpCstLeft))))
981               .bind("binop-const-compare-to-sym")),
982       this);
983 
984   // Match expressions like: x <op> 10 == x <op> 12.
985   Finder->addMatcher(
986       traverse(TK_AsIs,
987                binaryOperator(isComparisonOperator(), hasLHS(BinOpCstLeft),
988                               hasRHS(BinOpCstRight),
989                               // Already reported as redundant.
990                               unless(operandsAreEquivalent()))
991                    .bind("binop-const-compare-to-binop-const")),
992       this);
993 
994   // Match relational expressions combined with logical operators and find
995   // redundant sub-expressions.
996   // see: 'checkRelationalExpr'
997 
998   // Match expressions like: x < 2 && x > 2.
999   const auto ComparisonLeft = matchRelationalIntegerConstantExpr("lhs");
1000   const auto ComparisonRight = matchRelationalIntegerConstantExpr("rhs");
1001   Finder->addMatcher(
1002       traverse(TK_AsIs,
1003                binaryOperator(hasAnyOperatorName("||", "&&"),
1004                               hasLHS(ComparisonLeft), hasRHS(ComparisonRight),
1005                               // Already reported as redundant.
1006                               unless(operandsAreEquivalent()))
1007                    .bind("comparisons-of-symbol-and-const")),
1008       this);
1009 }
1010 
checkArithmeticExpr(const MatchFinder::MatchResult & Result)1011 void RedundantExpressionCheck::checkArithmeticExpr(
1012     const MatchFinder::MatchResult &Result) {
1013   APSInt LhsValue, RhsValue;
1014   const Expr *LhsSymbol = nullptr, *RhsSymbol = nullptr;
1015   BinaryOperatorKind LhsOpcode, RhsOpcode;
1016 
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,
1021                                           LhsValue) ||
1022         !retrieveSymbolicExpr(Result, "rhs", RhsSymbol) ||
1023         !areEquivalentExpr(LhsSymbol, RhsSymbol))
1024       return;
1025 
1026     // Check expressions: x + k == x  or  x - k == x.
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");
1036     }
1037   } else if (const auto *ComparisonOperator =
1038                  Result.Nodes.getNodeAs<BinaryOperator>(
1039                      "binop-const-compare-to-binop-const")) {
1040     BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1041 
1042     if (!retrieveBinOpIntegerConstantExpr(Result, "lhs", LhsOpcode, LhsSymbol,
1043                                           LhsValue) ||
1044         !retrieveBinOpIntegerConstantExpr(Result, "rhs", RhsOpcode, RhsSymbol,
1045                                           RhsValue) ||
1046         !areEquivalentExpr(LhsSymbol, RhsSymbol))
1047       return;
1048 
1049     transformSubToCanonicalAddExpr(LhsOpcode, LhsValue);
1050     transformSubToCanonicalAddExpr(RhsOpcode, RhsValue);
1051 
1052     // Check expressions: x + 1 == x + 2  or  x + 1 != x + 2.
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) ||
1060                  (Opcode == BO_NE &&
1061                   APSInt::compareValues(LhsValue, RhsValue) == 0)) {
1062         diag(ComparisonOperator->getOperatorLoc(),
1063              "logical expression is always false");
1064       }
1065     }
1066   }
1067 }
1068 
exprEvaluatesToZero(BinaryOperatorKind Opcode,APSInt Value)1069 static bool exprEvaluatesToZero(BinaryOperatorKind Opcode, APSInt Value) {
1070   return (Opcode == BO_And || Opcode == BO_AndAssign) && Value == 0;
1071 }
1072 
exprEvaluatesToBitwiseNegatedZero(BinaryOperatorKind Opcode,APSInt Value)1073 static bool exprEvaluatesToBitwiseNegatedZero(BinaryOperatorKind Opcode,
1074                                               APSInt Value) {
1075   return (Opcode == BO_Or || Opcode == BO_OrAssign) && ~Value == 0;
1076 }
1077 
exprEvaluatesToSymbolic(BinaryOperatorKind Opcode,APSInt Value)1078 static bool exprEvaluatesToSymbolic(BinaryOperatorKind Opcode, APSInt Value) {
1079   return ((Opcode == BO_Or || Opcode == BO_OrAssign) && Value == 0) ||
1080          ((Opcode == BO_And || Opcode == BO_AndAssign) && ~Value == 0);
1081 }
1082 
1083 
checkBitwiseExpr(const MatchFinder::MatchResult & Result)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();
1089 
1090     APSInt LhsValue, RhsValue;
1091     const Expr *LhsSymbol = nullptr;
1092     BinaryOperatorKind LhsOpcode;
1093     if (!retrieveBinOpIntegerConstantExpr(Result, "lhs", LhsOpcode, LhsSymbol,
1094                                           LhsValue) ||
1095         !retrieveIntegerConstantExpr(Result, "rhs", RhsValue))
1096       return;
1097 
1098     uint64_t LhsConstant = LhsValue.getZExtValue();
1099     uint64_t RhsConstant = RhsValue.getZExtValue();
1100     SourceLocation Loc = ComparisonOperator->getOperatorLoc();
1101 
1102     // Check expression: x & k1 == k2  (i.e. x & 0xFF == 0xF00)
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");
1108     }
1109 
1110     // Check expression: x | k1 == k2  (i.e. x | 0xFF == 0xF00)
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");
1116     }
1117   } else if (const auto *IneffectiveOperator =
1118                  Result.Nodes.getNodeAs<BinaryOperator>(
1119                      "ineffective-bitwise")) {
1120     APSInt Value;
1121     const Expr *Sym = nullptr, *ConstExpr = nullptr;
1122 
1123     if (!retrieveSymbolicExpr(Result, "ineffective-bitwise", Sym) ||
1124         !retrieveIntegerConstantExpr(Result, "ineffective-bitwise", Value,
1125                                      ConstExpr))
1126       return;
1127 
1128     if((Value != 0 && ~Value != 0) || Sym->getExprLoc().isMacroID())
1129         return;
1130 
1131     SourceLocation Loc = IneffectiveOperator->getOperatorLoc();
1132 
1133     BinaryOperatorKind Opcode = IneffectiveOperator->getOpcode();
1134     if (exprEvaluatesToZero(Opcode, Value)) {
1135       diag(Loc, "expression always evaluates to 0");
1136     } else if (exprEvaluatesToBitwiseNegatedZero(Opcode, Value)) {
1137       SourceRange ConstExprRange(ConstExpr->getBeginLoc(),
1138                                  ConstExpr->getEndLoc());
1139       StringRef ConstExprText = Lexer::getSourceText(
1140           CharSourceRange::getTokenRange(ConstExprRange), *Result.SourceManager,
1141           Result.Context->getLangOpts());
1142 
1143       diag(Loc, "expression always evaluates to '%0'") << ConstExprText;
1144 
1145     } else if (exprEvaluatesToSymbolic(Opcode, Value)) {
1146       SourceRange SymExprRange(Sym->getBeginLoc(), Sym->getEndLoc());
1147 
1148       StringRef ExprText = Lexer::getSourceText(
1149           CharSourceRange::getTokenRange(SymExprRange), *Result.SourceManager,
1150           Result.Context->getLangOpts());
1151 
1152       diag(Loc, "expression always evaluates to '%0'") << ExprText;
1153     }
1154   }
1155 }
1156 
checkRelationalExpr(const MatchFinder::MatchResult & Result)1157 void RedundantExpressionCheck::checkRelationalExpr(
1158     const MatchFinder::MatchResult &Result) {
1159   if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1160           "comparisons-of-symbol-and-const")) {
1161     // Matched expressions are: (x <op> k1) <REL> (x <op> k2).
1162     // E.g.: (X < 2) && (X > 4)
1163     BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1164 
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;
1170 
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))
1176       return;
1177 
1178     // Bring expr to a canonical form: smallest constant must be on the left.
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);
1184     }
1185 
1186     // Constants come from two different macros, or one of them is a macro.
1187     if (areExprsFromDifferentMacros(LhsConst, RhsConst, Result.Context) ||
1188         areExprsMacroAndNonMacro(LhsConst, RhsConst))
1189       return;
1190 
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");
1195       return;
1196     }
1197 
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");
1206       }
1207     }
1208 
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");
1217       }
1218     }
1219   }
1220 }
1221 
check(const MatchFinder::MatchResult & Result)1222 void RedundantExpressionCheck::check(const MatchFinder::MatchResult &Result) {
1223   if (const auto *BinOp = Result.Nodes.getNodeAs<BinaryOperator>("binary")) {
1224     // If the expression's constants are macros, check whether they are
1225     // intentional.
1226     if (areSidesBinaryConstExpressions(BinOp, Result.Context)) {
1227       const Expr *LhsConst = nullptr, *RhsConst = nullptr;
1228       BinaryOperatorKind MainOpcode, SideOpcode;
1229 
1230       if (!retrieveConstExprFromBothSides(BinOp, MainOpcode, SideOpcode,
1231                                           LhsConst, RhsConst, Result.Context))
1232         return;
1233 
1234       if (areExprsFromDifferentMacros(LhsConst, RhsConst, Result.Context) ||
1235           areExprsMacroAndNonMacro(LhsConst, RhsConst))
1236         return;
1237     }
1238 
1239     diag(BinOp->getOperatorLoc(), "both sides of operator are equivalent");
1240   }
1241 
1242   if (const auto *CondOp =
1243           Result.Nodes.getNodeAs<ConditionalOperator>("cond")) {
1244     const Expr *TrueExpr = CondOp->getTrueExpr();
1245     const Expr *FalseExpr = CondOp->getFalseExpr();
1246 
1247     if (areExprsFromDifferentMacros(TrueExpr, FalseExpr, Result.Context) ||
1248         areExprsMacroAndNonMacro(TrueExpr, FalseExpr))
1249       return;
1250     diag(CondOp->getColonLoc(),
1251          "'true' and 'false' expressions are equivalent");
1252   }
1253 
1254   if (const auto *Call = Result.Nodes.getNodeAs<CXXOperatorCallExpr>("call")) {
1255     if (canOverloadedOperatorArgsBeModified(Call, true))
1256       return;
1257 
1258     diag(Call->getOperatorLoc(),
1259          "both sides of overloaded operator are equivalent");
1260   }
1261 
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))
1265       return;
1266 
1267     StringRef Message =
1268         Call ? "overloaded operator has equivalent nested operands"
1269              : "operator has equivalent nested operands";
1270 
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();
1275     }
1276   }
1277 
1278   if (const auto *NegateOperator =
1279           Result.Nodes.getNodeAs<UnaryOperator>("logical-bitwise-confusion")) {
1280     SourceLocation OperatorLoc = NegateOperator->getOperatorLoc();
1281 
1282     auto Diag =
1283         diag(OperatorLoc,
1284              "ineffective logical negation operator used; did you mean '~'?");
1285     SourceLocation LogicalNotLocation = OperatorLoc.getLocWithOffset(1);
1286 
1287     if (!LogicalNotLocation.isMacroID())
1288       Diag << FixItHint::CreateReplacement(
1289           CharSourceRange::getCharRange(OperatorLoc, LogicalNotLocation), "~");
1290   }
1291 
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);
1298 
1299     if (!ShiftingValue)
1300       return;
1301 
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);
1306     if (!AndValue)
1307       return;
1308 
1309     // If ShiftingConst is shifted left with more bits than the position of the
1310     // leftmost 1 in the bit representation of AndValue, AndConstant is
1311     // ineffective.
1312     if (AndValue->getActiveBits() > *ShiftingValue)
1313       return;
1314 
1315     auto Diag = diag(BinaryAndExpr->getOperatorLoc(),
1316                      "ineffective bitwise and operation");
1317   }
1318 
1319   // Check for the following bound expressions:
1320   // - "binop-const-compare-to-sym",
1321   // - "binop-const-compare-to-binop-const",
1322   // Produced message:
1323   // -> "logical expression is always false/true"
1324   checkArithmeticExpr(Result);
1325 
1326   // Check for the following bound expression:
1327   // - "binop-const-compare-to-const",
1328   // - "ineffective-bitwise"
1329   // Produced message:
1330   // -> "logical expression is always false/true"
1331   // -> "expression always evaluates to ..."
1332   checkBitwiseExpr(Result);
1333 
1334   // Check for te following bound expression:
1335   // - "comparisons-of-symbol-and-const",
1336   // Produced messages:
1337   // -> "equivalent expression on both sides of logical operator",
1338   // -> "logical expression is always false/true"
1339   // -> "expression is redundant"
1340   checkRelationalExpr(Result);
1341 }
1342 
1343 } // namespace misc
1344 } // namespace tidy
1345 } // namespace clang
1346