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