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