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