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

source code of clang-tools-extra/clang-tidy/misc/RedundantExpressionCheck.cpp