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