1//===--- RedundantExpressionCheck.cpp - clang-tidy-------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "RedundantExpressionCheck.h"
10#include "../utils/Matchers.h"
11#include "../utils/OptionsUtils.h"
12#include "clang/AST/ASTContext.h"
13#include "clang/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(ID&: LeftID);
56 Right->Profile(ID&: 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(Left: dyn_cast_or_null<Expr>(Val: *LeftIter),
76 Right: dyn_cast_or_null<Expr>(Val: *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>(Val: Left)->getValue() ==
91 cast<CharacterLiteral>(Val: Right)->getValue();
92 case Stmt::IntegerLiteralClass: {
93 llvm::APInt LeftLit = cast<IntegerLiteral>(Val: Left)->getValue();
94 llvm::APInt RightLit = cast<IntegerLiteral>(Val: Right)->getValue();
95 return LeftLit.getBitWidth() == RightLit.getBitWidth() &&
96 LeftLit == RightLit;
97 }
98 case Stmt::FloatingLiteralClass:
99 return cast<FloatingLiteral>(Val: Left)->getValue().bitwiseIsEqual(
100 RHS: cast<FloatingLiteral>(Val: Right)->getValue());
101 case Stmt::StringLiteralClass:
102 return cast<StringLiteral>(Val: Left)->getBytes() ==
103 cast<StringLiteral>(Val: Right)->getBytes();
104 case Stmt::CXXOperatorCallExprClass:
105 return cast<CXXOperatorCallExpr>(Val: Left)->getOperator() ==
106 cast<CXXOperatorCallExpr>(Val: Right)->getOperator();
107 case Stmt::DependentScopeDeclRefExprClass:
108 if (cast<DependentScopeDeclRefExpr>(Val: Left)->getDeclName() !=
109 cast<DependentScopeDeclRefExpr>(Val: Right)->getDeclName())
110 return false;
111 return areEquivalentNameSpecifier(
112 Left: cast<DependentScopeDeclRefExpr>(Val: Left)->getQualifier(),
113 Right: cast<DependentScopeDeclRefExpr>(Val: Right)->getQualifier());
114 case Stmt::DeclRefExprClass:
115 return cast<DeclRefExpr>(Val: Left)->getDecl() ==
116 cast<DeclRefExpr>(Val: Right)->getDecl();
117 case Stmt::MemberExprClass:
118 return cast<MemberExpr>(Val: Left)->getMemberDecl() ==
119 cast<MemberExpr>(Val: Right)->getMemberDecl();
120 case Stmt::CXXFoldExprClass:
121 return cast<CXXFoldExpr>(Val: Left)->getOperator() ==
122 cast<CXXFoldExpr>(Val: Right)->getOperator();
123 case Stmt::CXXFunctionalCastExprClass:
124 case Stmt::CStyleCastExprClass:
125 return cast<ExplicitCastExpr>(Val: Left)->getTypeAsWritten() ==
126 cast<ExplicitCastExpr>(Val: 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>(Val: Left)->isIncrementDecrementOp())
133 return false;
134 return cast<UnaryOperator>(Val: Left)->getOpcode() ==
135 cast<UnaryOperator>(Val: Right)->getOpcode();
136 case Stmt::BinaryOperatorClass:
137 if (cast<BinaryOperator>(Val: Left)->isAssignmentOp())
138 return false;
139 return cast<BinaryOperator>(Val: Left)->getOpcode() ==
140 cast<BinaryOperator>(Val: Right)->getOpcode();
141 case Stmt::UnaryExprOrTypeTraitExprClass:
142 const auto *LeftUnaryExpr =
143 cast<UnaryExprOrTypeTraitExpr>(Val: Left);
144 const auto *RightUnaryExpr =
145 cast<UnaryExprOrTypeTraitExpr>(Val: 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(Left: LeftUnaryExpr->getArgumentExpr(),
152 Right: 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(I1: ValueLHS, I2: 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(Value: ValueLHS, Result&: ValueLhsPlus1) &&
175 APSInt::compareValues(I1: ValueLhsPlus1, I2: 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(I1: ValueLHS, I2: 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(Value: ValueLHS, Result&: ValueLhsPlus1) &&
216 APSInt::compareValues(I1: ValueLhsPlus1, I2: 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(I1: ValueLHS, I2: 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(Value: ValueLHS, Result&: ValueLhsPlus1) &&
255 APSInt::compareValues(I1: ValueLhsPlus1, I2: 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(I1: ValueLHS, I2: 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(Opc: 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(Left: Operands.first, Right: 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(Node: *TheExpr);
371 for (DynTypedNode DynParent : Parents) {
372 if (const auto *Parent = DynParent.get<Expr>()) {
373 bool Skip = isa<ParenExpr>(Val: Parent) || isa<ImplicitCastExpr>(Val: Parent) ||
374 isa<FullExpr>(Val: Parent) ||
375 isa<MaterializeTemporaryExpr>(Val: 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(Ctx: Context))
420 break;
421
422 if (areEquivalentExpr(Left: AllOperands[I], Right: AllOperands[J])) {
423 FoundDuplicates = true;
424 Duplicates.set(J);
425 Builder->setBinding(Id: SmallString<11>(llvm::formatv(Fmt: "duplicate{0}", Vals&: J)),
426 DynNode: DynTypedNode::create(Node: *AllOperands[J]));
427 }
428 }
429
430 if (FoundDuplicates)
431 Builder->setBinding(Id: SmallString<11>(llvm::formatv(Fmt: "duplicate{0}", Vals&: I)),
432 DynNode: DynTypedNode::create(Node: *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(Ctx: Finder->getASTContext());
442}
443
444AST_MATCHER(BinaryOperator, operandsAreEquivalent) {
445 return areEquivalentExpr(Left: Node.getLHS(), Right: Node.getRHS());
446}
447
448AST_MATCHER(BinaryOperator, nestedOperandsAreEquivalent) {
449 return markDuplicateOperands(TheExpr: &Node, Builder, Context&: Finder->getASTContext());
450}
451
452AST_MATCHER(ConditionalOperator, expressionsAreEquivalent) {
453 return areEquivalentExpr(Left: Node.getTrueExpr(), Right: Node.getFalseExpr());
454}
455
456AST_MATCHER(CallExpr, parametersAreEquivalent) {
457 return Node.getNumArgs() == 2 &&
458 areEquivalentExpr(Left: Node.getArg(Arg: 0), Right: Node.getArg(Arg: 1));
459}
460
461AST_MATCHER(CXXOperatorCallExpr, nestedParametersAreEquivalent) {
462 return markDuplicateOperands(TheExpr: &Node, Builder, Context&: 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, LangOpts: LO);
481 if (llvm::is_contained(Range: Names, Element: 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(ID: 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>(ID: CstId);
503 if (!ConstExpr)
504 return false;
505 std::optional<llvm::APSInt> R =
506 ConstExpr->getIntegerConstantExpr(Ctx: *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 InnerMatcher: expr(unless(isIntegerConstantExpr())).bind(ID: 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>(ID: 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(Matcher1: matchSymbolicExpr(Id),
547 Matcher2: matchIntegerConstantExpr(Id))),
548 binaryOperator(hasOperatorName(Name: "-"),
549 hasLHS(InnerMatcher: matchSymbolicExpr(Id)),
550 hasRHS(InnerMatcher: matchIntegerConstantExpr(Id)))))
551 .bind(ID: Id);
552 return ignoringParenImpCasts(InnerMatcher: 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: Id)) {
562 Opcode = BinExpr->getOpcode();
563 return retrieveSymbolicExpr(Result, Id, SymExpr&: 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(InnerMatcher: binaryOperator(
579 isComparisonOperator(), expr().bind(ID: Id),
580 anyOf(allOf(hasLHS(InnerMatcher: matchSymbolicExpr(Id)),
581 hasRHS(InnerMatcher: matchIntegerConstantExpr(Id))),
582 allOf(hasLHS(InnerMatcher: matchIntegerConstantExpr(Id)),
583 hasRHS(InnerMatcher: matchSymbolicExpr(Id)), expr().bind(ID: 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(Kind: CK_IntegralToBoolean),
589 hasSourceExpression(InnerMatcher: matchSymbolicExpr(Id)))
590 .bind(ID: CastId);
591
592 const auto NegateRelationalExpr =
593 unaryOperator(hasOperatorName(Name: "!"),
594 hasUnaryOperand(InnerMatcher: anyOf(CastExpr, RelationalExpr)))
595 .bind(ID: NegateId);
596
597 // Do not bind to double negation.
598 const auto NegateNegateRelationalExpr =
599 unaryOperator(hasOperatorName(Name: "!"),
600 hasUnaryOperand(InnerMatcher: unaryOperator(
601 hasOperatorName(Name: "!"),
602 hasUnaryOperand(InnerMatcher: 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(InnerMatcher: ignoringParenImpCasts(InnerMatcher: integerLiteral().bind(ID: ConstId))),
610 hasRHS(InnerMatcher: ignoringParenImpCasts(InnerMatcher: integerLiteral().bind(ID: ConstId)))))
611 .bind(ID: 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: 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>(ID: 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>(ID: OverloadId)) {
681 if (canOverloadedOperatorArgsBeModified(OperatorCall: OverloadedOperatorExpr, CheckSecondParam: 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(OO: OverloadedOperatorExpr->getOperator());
703
704 if (!retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr))
705 return false;
706
707 if (!BinaryOperator::isComparisonOp(Opc: 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(Opc: Opcode);
714
715 return true;
716 } else {
717 return false;
718 }
719
720 if (!retrieveSymbolicExpr(Result, Id, SymExpr&: Symbol))
721 return false;
722
723 if (Result.Nodes.getNodeAs<Expr>(ID: SwapId))
724 Opcode = BinaryOperator::reverseComparisonOp(Opc: Opcode);
725 if (Result.Nodes.getNodeAs<Expr>(ID: NegateId))
726 Opcode = BinaryOperator::negateComparisonOp(Opc: 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>(Val: BinOp->getLHS());
733 const auto *RhsBinOp = dyn_cast<BinaryOperator>(Val: BinOp->getRHS());
734
735 if (!LhsBinOp || !RhsBinOp)
736 return false;
737
738 auto IsIntegerConstantExpr = [AstCtx](const Expr *E) {
739 return !E->isValueDependent() && E->isIntegerConstantExpr(Ctx: *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>(Val: BinOp->getLHS());
765 const auto *BinOpRhs = cast<BinaryOperator>(Val: BinOp->getRHS());
766
767 auto IsIntegerConstantExpr = [AstCtx](const Expr *E) {
768 return !E->isValueDependent() && E->isIntegerConstantExpr(Ctx: *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(K: tok::raw_identifier))
792 return true;
793 if (T1.getLength() != T2.getLength())
794 return false;
795 return StringRef(SM.getCharacterData(SL: T1.getLocation()), T1.getLength()) ==
796 StringRef(SM.getCharacterData(SL: T2.getLocation()), T2.getLength());
797}
798
799bool isTokAtEndOfExpr(SourceRange ExprSR, Token T, const SourceManager &SM) {
800 return SM.getExpansionLoc(Loc: 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(Loc: SM.getExpansionLoc(Loc: Lsr.getBegin()));
821 std::pair<FileID, unsigned> RsrLocInfo =
822 SM.getDecomposedLoc(Loc: SM.getExpansionLoc(Loc: Rsr.getBegin()));
823 llvm::MemoryBufferRef MB = SM.getBufferOrFake(FID: LsrLocInfo.first);
824
825 const char *LTokenPos = MB.getBufferStart() + LsrLocInfo.second;
826 const char *RTokenPos = MB.getBufferStart() + RsrLocInfo.second;
827 Lexer LRawLex(SM.getLocForStartOfFile(FID: LsrLocInfo.first), LO,
828 MB.getBufferStart(), LTokenPos, MB.getBufferEnd());
829 Lexer RRawLex(SM.getLocForStartOfFile(FID: 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(Result&: LTok);
835 RRawLex.LexFromRawLexer(Result&: RTok);
836 } while (!LTok.is(K: tok::eof) && !RTok.is(K: tok::eof) &&
837 isSameRawIdentifierToken(T1: LTok, T2: RTok, SM) &&
838 !isTokAtEndOfExpr(ExprSR: Lsr, T: LTok, SM) &&
839 !isTokAtEndOfExpr(ExprSR: Rsr, T: RTok, SM));
840 return (!isTokAtEndOfExpr(ExprSR: Lsr, T: LTok, SM) ||
841 !isTokAtEndOfExpr(ExprSR: Rsr, T: RTok, SM)) ||
842 !isSameRawIdentifierToken(T1: LTok, T2: 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
857void RedundantExpressionCheck::registerMatchers(MatchFinder *Finder) {
858 const auto AnyLiteralExpr = ignoringParenImpCasts(
859 InnerMatcher: anyOf(cxxBoolLiteral(), characterLiteral(), integerLiteral()));
860
861 const auto BannedIntegerLiteral =
862 integerLiteral(expandedByMacro(Names: KnownBannedMacroNames));
863 const auto IsInUnevaluatedContext = expr(anyOf(
864 hasAncestor(expr(hasUnevaluatedContext())), hasAncestor(typeLoc())));
865
866 // Binary with equivalent operands, like (X != 2 && X != 2).
867 Finder->addMatcher(
868 NodeMatch: traverse(TK: TK_AsIs,
869 InnerMatcher: binaryOperator(
870 anyOf(isComparisonOperator(),
871 hasAnyOperatorName("-", "/", "%", "|", "&", "^", "&&",
872 "||", "=")),
873 operandsAreEquivalent(),
874 // Filter noisy false positives.
875 unless(isInTemplateInstantiation()),
876 unless(binaryOperatorIsInMacro()),
877 unless(hasType(InnerMatcher: realFloatingPointType())),
878 unless(hasEitherOperand(InnerMatcher: hasType(InnerMatcher: realFloatingPointType()))),
879 unless(hasLHS(InnerMatcher: AnyLiteralExpr)),
880 unless(hasDescendant(BannedIntegerLiteral)),
881 unless(IsInUnevaluatedContext))
882 .bind(ID: "binary")),
883 Action: this);
884
885 // Logical or bitwise operator with equivalent nested operands, like (X && Y
886 // && X) or (X && (Y && X))
887 Finder->addMatcher(
888 NodeMatch: binaryOperator(hasAnyOperatorName("|", "&", "||", "&&", "^"),
889 nestedOperandsAreEquivalent(),
890 // Filter noisy false positives.
891 unless(isInTemplateInstantiation()),
892 unless(binaryOperatorIsInMacro()),
893 // TODO: if the banned macros are themselves duplicated
894 unless(hasDescendant(BannedIntegerLiteral)),
895 unless(IsInUnevaluatedContext))
896 .bind(ID: "nested-duplicates"),
897 Action: this);
898
899 // Conditional (ternary) operator with equivalent operands, like (Y ? X : X).
900 Finder->addMatcher(
901 NodeMatch: traverse(TK: TK_AsIs,
902 InnerMatcher: conditionalOperator(expressionsAreEquivalent(),
903 // Filter noisy false positives.
904 unless(conditionalOperatorIsInMacro()),
905 unless(isInTemplateInstantiation()),
906 unless(IsInUnevaluatedContext))
907 .bind(ID: "cond")),
908 Action: this);
909
910 // Overloaded operators with equivalent operands.
911 Finder->addMatcher(
912 NodeMatch: traverse(TK: TK_AsIs,
913 InnerMatcher: cxxOperatorCallExpr(
914 hasAnyOverloadedOperatorName("-", "/", "%", "|", "&", "^",
915 "==", "!=", "<", "<=", ">",
916 ">=", "&&", "||", "="),
917 parametersAreEquivalent(),
918 // Filter noisy false positives.
919 unless(isMacro()), unless(isInTemplateInstantiation()),
920 unless(IsInUnevaluatedContext))
921 .bind(ID: "call")),
922 Action: this);
923
924 // Overloaded operators with equivalent operands.
925 Finder->addMatcher(
926 NodeMatch: cxxOperatorCallExpr(
927 hasAnyOverloadedOperatorName("|", "&", "||", "&&", "^"),
928 nestedParametersAreEquivalent(), argumentCountIs(N: 2),
929 // Filter noisy false positives.
930 unless(isMacro()), unless(isInTemplateInstantiation()),
931 unless(IsInUnevaluatedContext))
932 .bind(ID: "nested-duplicates"),
933 Action: this);
934
935 // Match expressions like: !(1 | 2 | 3)
936 Finder->addMatcher(
937 NodeMatch: traverse(TK: TK_AsIs,
938 InnerMatcher: implicitCastExpr(
939 hasImplicitDestinationType(InnerMatcher: isInteger()),
940 has(unaryOperator(
941 hasOperatorName(Name: "!"),
942 hasUnaryOperand(InnerMatcher: ignoringParenImpCasts(InnerMatcher: binaryOperator(
943 hasAnyOperatorName("|", "&"),
944 hasLHS(InnerMatcher: anyOf(
945 binaryOperator(hasAnyOperatorName("|", "&")),
946 integerLiteral())),
947 hasRHS(InnerMatcher: integerLiteral())))))
948 .bind(ID: "logical-bitwise-confusion")),
949 unless(IsInUnevaluatedContext))),
950 Action: this);
951
952 // Match expressions like: (X << 8) & 0xFF
953 Finder->addMatcher(
954 NodeMatch: traverse(TK: TK_AsIs,
955 InnerMatcher: binaryOperator(
956 hasOperatorName(Name: "&"),
957 hasOperands(Matcher1: ignoringParenImpCasts(InnerMatcher: binaryOperator(
958 hasOperatorName(Name: "<<"),
959 hasRHS(InnerMatcher: ignoringParenImpCasts(
960 InnerMatcher: integerLiteral().bind(ID: "shift-const"))))),
961 Matcher2: ignoringParenImpCasts(
962 InnerMatcher: integerLiteral().bind(ID: "and-const"))),
963 unless(IsInUnevaluatedContext))
964 .bind(ID: "left-right-shift-confusion")),
965 Action: this);
966
967 // Match common expressions and apply more checks to find redundant
968 // sub-expressions.
969 // a) Expr <op> K1 == K2
970 // b) Expr <op> K1 == Expr
971 // c) Expr <op> K1 == Expr <op> K2
972 // see: 'checkArithmeticExpr' and 'checkBitwiseExpr'
973 const auto BinOpCstLeft = matchBinOpIntegerConstantExpr(Id: "lhs");
974 const auto BinOpCstRight = matchBinOpIntegerConstantExpr(Id: "rhs");
975 const auto CstRight = matchIntegerConstantExpr(Id: "rhs");
976 const auto SymRight = matchSymbolicExpr(Id: "rhs");
977
978 // Match expressions like: x <op> 0xFF == 0xF00.
979 Finder->addMatcher(
980 NodeMatch: traverse(TK: TK_AsIs, InnerMatcher: binaryOperator(isComparisonOperator(),
981 hasOperands(Matcher1: BinOpCstLeft, Matcher2: CstRight),
982 unless(IsInUnevaluatedContext))
983 .bind(ID: "binop-const-compare-to-const")),
984 Action: this);
985
986 // Match expressions like: x <op> 0xFF == x.
987 Finder->addMatcher(
988 NodeMatch: traverse(
989 TK: TK_AsIs,
990 InnerMatcher: binaryOperator(isComparisonOperator(),
991 anyOf(allOf(hasLHS(InnerMatcher: BinOpCstLeft), hasRHS(InnerMatcher: SymRight)),
992 allOf(hasLHS(InnerMatcher: SymRight), hasRHS(InnerMatcher: BinOpCstLeft))),
993 unless(IsInUnevaluatedContext))
994 .bind(ID: "binop-const-compare-to-sym")),
995 Action: this);
996
997 // Match expressions like: x <op> 10 == x <op> 12.
998 Finder->addMatcher(
999 NodeMatch: traverse(TK: TK_AsIs,
1000 InnerMatcher: binaryOperator(isComparisonOperator(), hasLHS(InnerMatcher: BinOpCstLeft),
1001 hasRHS(InnerMatcher: BinOpCstRight),
1002 // Already reported as redundant.
1003 unless(operandsAreEquivalent()),
1004 unless(IsInUnevaluatedContext))
1005 .bind(ID: "binop-const-compare-to-binop-const")),
1006 Action: this);
1007
1008 // Match relational expressions combined with logical operators and find
1009 // redundant sub-expressions.
1010 // see: 'checkRelationalExpr'
1011
1012 // Match expressions like: x < 2 && x > 2.
1013 const auto ComparisonLeft = matchRelationalIntegerConstantExpr(Id: "lhs");
1014 const auto ComparisonRight = matchRelationalIntegerConstantExpr(Id: "rhs");
1015 Finder->addMatcher(
1016 NodeMatch: traverse(TK: TK_AsIs,
1017 InnerMatcher: binaryOperator(hasAnyOperatorName("||", "&&"),
1018 hasLHS(InnerMatcher: ComparisonLeft), hasRHS(InnerMatcher: ComparisonRight),
1019 // Already reported as redundant.
1020 unless(operandsAreEquivalent()),
1021 unless(IsInUnevaluatedContext))
1022 .bind(ID: "comparisons-of-symbol-and-const")),
1023 Action: this);
1024}
1025
1026void RedundantExpressionCheck::checkArithmeticExpr(
1027 const MatchFinder::MatchResult &Result) {
1028 APSInt LhsValue, RhsValue;
1029 const Expr *LhsSymbol = nullptr, *RhsSymbol = nullptr;
1030 BinaryOperatorKind LhsOpcode{}, RhsOpcode{};
1031
1032 if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1033 ID: "binop-const-compare-to-sym")) {
1034 BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1035 if (!retrieveBinOpIntegerConstantExpr(Result, Id: "lhs", Opcode&: LhsOpcode, Symbol&: LhsSymbol,
1036 Value&: LhsValue) ||
1037 !retrieveSymbolicExpr(Result, Id: "rhs", SymExpr&: RhsSymbol) ||
1038 !areEquivalentExpr(Left: LhsSymbol, Right: RhsSymbol))
1039 return;
1040
1041 // Check expressions: x + k == x or x - k == x.
1042 if (LhsOpcode == BO_Add || LhsOpcode == BO_Sub) {
1043 if ((LhsValue != 0 && Opcode == BO_EQ) ||
1044 (LhsValue == 0 && Opcode == BO_NE))
1045 diag(Loc: ComparisonOperator->getOperatorLoc(),
1046 Description: "logical expression is always false");
1047 else if ((LhsValue == 0 && Opcode == BO_EQ) ||
1048 (LhsValue != 0 && Opcode == BO_NE))
1049 diag(Loc: ComparisonOperator->getOperatorLoc(),
1050 Description: "logical expression is always true");
1051 }
1052 } else if (const auto *ComparisonOperator =
1053 Result.Nodes.getNodeAs<BinaryOperator>(
1054 ID: "binop-const-compare-to-binop-const")) {
1055 BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1056
1057 if (!retrieveBinOpIntegerConstantExpr(Result, Id: "lhs", Opcode&: LhsOpcode, Symbol&: LhsSymbol,
1058 Value&: LhsValue) ||
1059 !retrieveBinOpIntegerConstantExpr(Result, Id: "rhs", Opcode&: RhsOpcode, Symbol&: RhsSymbol,
1060 Value&: RhsValue) ||
1061 !areEquivalentExpr(Left: LhsSymbol, Right: RhsSymbol))
1062 return;
1063
1064 transformSubToCanonicalAddExpr(Opcode&: LhsOpcode, Value&: LhsValue);
1065 transformSubToCanonicalAddExpr(Opcode&: RhsOpcode, Value&: RhsValue);
1066
1067 // Check expressions: x + 1 == x + 2 or x + 1 != x + 2.
1068 if (LhsOpcode == BO_Add && RhsOpcode == BO_Add) {
1069 if ((Opcode == BO_EQ && APSInt::compareValues(I1: LhsValue, I2: RhsValue) == 0) ||
1070 (Opcode == BO_NE && APSInt::compareValues(I1: LhsValue, I2: RhsValue) != 0)) {
1071 diag(Loc: ComparisonOperator->getOperatorLoc(),
1072 Description: "logical expression is always true");
1073 } else if ((Opcode == BO_EQ &&
1074 APSInt::compareValues(I1: LhsValue, I2: RhsValue) != 0) ||
1075 (Opcode == BO_NE &&
1076 APSInt::compareValues(I1: LhsValue, I2: RhsValue) == 0)) {
1077 diag(Loc: ComparisonOperator->getOperatorLoc(),
1078 Description: "logical expression is always false");
1079 }
1080 }
1081 }
1082}
1083
1084static bool exprEvaluatesToZero(BinaryOperatorKind Opcode, APSInt Value) {
1085 return (Opcode == BO_And || Opcode == BO_AndAssign) && Value == 0;
1086}
1087
1088static bool exprEvaluatesToBitwiseNegatedZero(BinaryOperatorKind Opcode,
1089 APSInt Value) {
1090 return (Opcode == BO_Or || Opcode == BO_OrAssign) && ~Value == 0;
1091}
1092
1093static bool exprEvaluatesToSymbolic(BinaryOperatorKind Opcode, APSInt Value) {
1094 return ((Opcode == BO_Or || Opcode == BO_OrAssign) && Value == 0) ||
1095 ((Opcode == BO_And || Opcode == BO_AndAssign) && ~Value == 0);
1096}
1097
1098
1099void RedundantExpressionCheck::checkBitwiseExpr(
1100 const MatchFinder::MatchResult &Result) {
1101 if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1102 ID: "binop-const-compare-to-const")) {
1103 BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1104
1105 APSInt LhsValue, RhsValue;
1106 const Expr *LhsSymbol = nullptr;
1107 BinaryOperatorKind LhsOpcode{};
1108 if (!retrieveBinOpIntegerConstantExpr(Result, Id: "lhs", Opcode&: LhsOpcode, Symbol&: LhsSymbol,
1109 Value&: LhsValue) ||
1110 !retrieveIntegerConstantExpr(Result, Id: "rhs", Value&: RhsValue))
1111 return;
1112
1113 uint64_t LhsConstant = LhsValue.getZExtValue();
1114 uint64_t RhsConstant = RhsValue.getZExtValue();
1115 SourceLocation Loc = ComparisonOperator->getOperatorLoc();
1116
1117 // Check expression: x & k1 == k2 (i.e. x & 0xFF == 0xF00)
1118 if (LhsOpcode == BO_And && (LhsConstant & RhsConstant) != RhsConstant) {
1119 if (Opcode == BO_EQ)
1120 diag(Loc, Description: "logical expression is always false");
1121 else if (Opcode == BO_NE)
1122 diag(Loc, Description: "logical expression is always true");
1123 }
1124
1125 // Check expression: x | k1 == k2 (i.e. x | 0xFF == 0xF00)
1126 if (LhsOpcode == BO_Or && (LhsConstant | RhsConstant) != RhsConstant) {
1127 if (Opcode == BO_EQ)
1128 diag(Loc, Description: "logical expression is always false");
1129 else if (Opcode == BO_NE)
1130 diag(Loc, Description: "logical expression is always true");
1131 }
1132 } else if (const auto *IneffectiveOperator =
1133 Result.Nodes.getNodeAs<BinaryOperator>(
1134 ID: "ineffective-bitwise")) {
1135 APSInt Value;
1136 const Expr *Sym = nullptr, *ConstExpr = nullptr;
1137
1138 if (!retrieveSymbolicExpr(Result, Id: "ineffective-bitwise", SymExpr&: Sym) ||
1139 !retrieveIntegerConstantExpr(Result, Id: "ineffective-bitwise", Value,
1140 ConstExpr))
1141 return;
1142
1143 if((Value != 0 && ~Value != 0) || Sym->getExprLoc().isMacroID())
1144 return;
1145
1146 SourceLocation Loc = IneffectiveOperator->getOperatorLoc();
1147
1148 BinaryOperatorKind Opcode = IneffectiveOperator->getOpcode();
1149 if (exprEvaluatesToZero(Opcode, Value)) {
1150 diag(Loc, Description: "expression always evaluates to 0");
1151 } else if (exprEvaluatesToBitwiseNegatedZero(Opcode, Value)) {
1152 SourceRange ConstExprRange(ConstExpr->getBeginLoc(),
1153 ConstExpr->getEndLoc());
1154 StringRef ConstExprText = Lexer::getSourceText(
1155 Range: CharSourceRange::getTokenRange(R: ConstExprRange), SM: *Result.SourceManager,
1156 LangOpts: Result.Context->getLangOpts());
1157
1158 diag(Loc, Description: "expression always evaluates to '%0'") << ConstExprText;
1159
1160 } else if (exprEvaluatesToSymbolic(Opcode, Value)) {
1161 SourceRange SymExprRange(Sym->getBeginLoc(), Sym->getEndLoc());
1162
1163 StringRef ExprText = Lexer::getSourceText(
1164 Range: CharSourceRange::getTokenRange(R: SymExprRange), SM: *Result.SourceManager,
1165 LangOpts: Result.Context->getLangOpts());
1166
1167 diag(Loc, Description: "expression always evaluates to '%0'") << ExprText;
1168 }
1169 }
1170}
1171
1172void RedundantExpressionCheck::checkRelationalExpr(
1173 const MatchFinder::MatchResult &Result) {
1174 if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
1175 ID: "comparisons-of-symbol-and-const")) {
1176 // Matched expressions are: (x <op> k1) <REL> (x <op> k2).
1177 // E.g.: (X < 2) && (X > 4)
1178 BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
1179
1180 const Expr *LhsExpr = nullptr, *RhsExpr = nullptr;
1181 const Expr *LhsSymbol = nullptr, *RhsSymbol = nullptr;
1182 const Expr *LhsConst = nullptr, *RhsConst = nullptr;
1183 BinaryOperatorKind LhsOpcode{}, RhsOpcode{};
1184 APSInt LhsValue, RhsValue;
1185
1186 if (!retrieveRelationalIntegerConstantExpr(
1187 Result, Id: "lhs", OperandExpr&: LhsExpr, Opcode&: LhsOpcode, Symbol&: LhsSymbol, Value&: LhsValue, ConstExpr&: LhsConst) ||
1188 !retrieveRelationalIntegerConstantExpr(
1189 Result, Id: "rhs", OperandExpr&: RhsExpr, Opcode&: RhsOpcode, Symbol&: RhsSymbol, Value&: RhsValue, ConstExpr&: RhsConst) ||
1190 !areEquivalentExpr(Left: LhsSymbol, Right: RhsSymbol))
1191 return;
1192
1193 // Bring expr to a canonical form: smallest constant must be on the left.
1194 if (APSInt::compareValues(I1: LhsValue, I2: RhsValue) > 0) {
1195 std::swap(a&: LhsExpr, b&: RhsExpr);
1196 std::swap(a&: LhsValue, b&: RhsValue);
1197 std::swap(a&: LhsSymbol, b&: RhsSymbol);
1198 std::swap(a&: LhsOpcode, b&: RhsOpcode);
1199 }
1200
1201 // Constants come from two different macros, or one of them is a macro.
1202 if (areExprsFromDifferentMacros(LhsExpr: LhsConst, RhsExpr: RhsConst, AstCtx: Result.Context) ||
1203 areExprsMacroAndNonMacro(LhsExpr&: LhsConst, RhsExpr&: RhsConst))
1204 return;
1205
1206 if ((Opcode == BO_LAnd || Opcode == BO_LOr) &&
1207 areEquivalentRanges(OpcodeLHS: LhsOpcode, ValueLHS: LhsValue, OpcodeRHS: RhsOpcode, ValueRHS: RhsValue)) {
1208 diag(Loc: ComparisonOperator->getOperatorLoc(),
1209 Description: "equivalent expression on both sides of logical operator");
1210 return;
1211 }
1212
1213 if (Opcode == BO_LAnd) {
1214 if (areExclusiveRanges(OpcodeLHS: LhsOpcode, ValueLHS: LhsValue, OpcodeRHS: RhsOpcode, ValueRHS: RhsValue)) {
1215 diag(Loc: ComparisonOperator->getOperatorLoc(),
1216 Description: "logical expression is always false");
1217 } else if (rangeSubsumesRange(OpcodeLHS: LhsOpcode, ValueLHS: LhsValue, OpcodeRHS: RhsOpcode, ValueRHS: RhsValue)) {
1218 diag(Loc: LhsExpr->getExprLoc(), Description: "expression is redundant");
1219 } else if (rangeSubsumesRange(OpcodeLHS: RhsOpcode, ValueLHS: RhsValue, OpcodeRHS: LhsOpcode, ValueRHS: LhsValue)) {
1220 diag(Loc: RhsExpr->getExprLoc(), Description: "expression is redundant");
1221 }
1222 }
1223
1224 if (Opcode == BO_LOr) {
1225 if (rangesFullyCoverDomain(OpcodeLHS: LhsOpcode, ValueLHS: LhsValue, OpcodeRHS: RhsOpcode, ValueRHS: RhsValue)) {
1226 diag(Loc: ComparisonOperator->getOperatorLoc(),
1227 Description: "logical expression is always true");
1228 } else if (rangeSubsumesRange(OpcodeLHS: LhsOpcode, ValueLHS: LhsValue, OpcodeRHS: RhsOpcode, ValueRHS: RhsValue)) {
1229 diag(Loc: RhsExpr->getExprLoc(), Description: "expression is redundant");
1230 } else if (rangeSubsumesRange(OpcodeLHS: RhsOpcode, ValueLHS: RhsValue, OpcodeRHS: LhsOpcode, ValueRHS: LhsValue)) {
1231 diag(Loc: LhsExpr->getExprLoc(), Description: "expression is redundant");
1232 }
1233 }
1234 }
1235}
1236
1237void RedundantExpressionCheck::check(const MatchFinder::MatchResult &Result) {
1238 if (const auto *BinOp = Result.Nodes.getNodeAs<BinaryOperator>(ID: "binary")) {
1239 // If the expression's constants are macros, check whether they are
1240 // intentional.
1241 if (areSidesBinaryConstExpressions(BinOp, AstCtx: Result.Context)) {
1242 const Expr *LhsConst = nullptr, *RhsConst = nullptr;
1243 BinaryOperatorKind MainOpcode{}, SideOpcode{};
1244
1245 if (!retrieveConstExprFromBothSides(BinOp, MainOpcode, SideOpcode,
1246 LhsConst, RhsConst, AstCtx: Result.Context))
1247 return;
1248
1249 if (areExprsFromDifferentMacros(LhsExpr: LhsConst, RhsExpr: RhsConst, AstCtx: Result.Context) ||
1250 areExprsMacroAndNonMacro(LhsExpr&: LhsConst, RhsExpr&: RhsConst))
1251 return;
1252 }
1253
1254 diag(Loc: BinOp->getOperatorLoc(), Description: "both sides of operator are equivalent");
1255 }
1256
1257 if (const auto *CondOp =
1258 Result.Nodes.getNodeAs<ConditionalOperator>(ID: "cond")) {
1259 const Expr *TrueExpr = CondOp->getTrueExpr();
1260 const Expr *FalseExpr = CondOp->getFalseExpr();
1261
1262 if (areExprsFromDifferentMacros(LhsExpr: TrueExpr, RhsExpr: FalseExpr, AstCtx: Result.Context) ||
1263 areExprsMacroAndNonMacro(LhsExpr&: TrueExpr, RhsExpr&: FalseExpr))
1264 return;
1265 diag(CondOp->getColonLoc(),
1266 "'true' and 'false' expressions are equivalent");
1267 }
1268
1269 if (const auto *Call = Result.Nodes.getNodeAs<CXXOperatorCallExpr>(ID: "call")) {
1270 if (canOverloadedOperatorArgsBeModified(OperatorCall: Call, CheckSecondParam: true))
1271 return;
1272
1273 diag(Loc: Call->getOperatorLoc(),
1274 Description: "both sides of overloaded operator are equivalent");
1275 }
1276
1277 if (const auto *Op = Result.Nodes.getNodeAs<Expr>(ID: "nested-duplicates")) {
1278 const auto *Call = dyn_cast<CXXOperatorCallExpr>(Val: Op);
1279 if (Call && canOverloadedOperatorArgsBeModified(OperatorCall: Call, CheckSecondParam: true))
1280 return;
1281
1282 StringRef Message =
1283 Call ? "overloaded operator has equivalent nested operands"
1284 : "operator has equivalent nested operands";
1285
1286 const auto Diag = diag(Loc: Op->getExprLoc(), Description: Message);
1287 for (const auto &KeyValue : Result.Nodes.getMap()) {
1288 if (StringRef(KeyValue.first).starts_with(Prefix: "duplicate"))
1289 Diag << KeyValue.second.getSourceRange();
1290 }
1291 }
1292
1293 if (const auto *NegateOperator =
1294 Result.Nodes.getNodeAs<UnaryOperator>(ID: "logical-bitwise-confusion")) {
1295 SourceLocation OperatorLoc = NegateOperator->getOperatorLoc();
1296
1297 auto Diag =
1298 diag(Loc: OperatorLoc,
1299 Description: "ineffective logical negation operator used; did you mean '~'?");
1300 SourceLocation LogicalNotLocation = OperatorLoc.getLocWithOffset(Offset: 1);
1301
1302 if (!LogicalNotLocation.isMacroID())
1303 Diag << FixItHint::CreateReplacement(
1304 RemoveRange: CharSourceRange::getCharRange(B: OperatorLoc, E: LogicalNotLocation), Code: "~");
1305 }
1306
1307 if (const auto *BinaryAndExpr = Result.Nodes.getNodeAs<BinaryOperator>(
1308 ID: "left-right-shift-confusion")) {
1309 const auto *ShiftingConst = Result.Nodes.getNodeAs<Expr>(ID: "shift-const");
1310 assert(ShiftingConst && "Expr* 'ShiftingConst' is nullptr!");
1311 std::optional<llvm::APSInt> ShiftingValue =
1312 ShiftingConst->getIntegerConstantExpr(Ctx: *Result.Context);
1313
1314 if (!ShiftingValue)
1315 return;
1316
1317 const auto *AndConst = Result.Nodes.getNodeAs<Expr>(ID: "and-const");
1318 assert(AndConst && "Expr* 'AndCont' is nullptr!");
1319 std::optional<llvm::APSInt> AndValue =
1320 AndConst->getIntegerConstantExpr(Ctx: *Result.Context);
1321 if (!AndValue)
1322 return;
1323
1324 // If ShiftingConst is shifted left with more bits than the position of the
1325 // leftmost 1 in the bit representation of AndValue, AndConstant is
1326 // ineffective.
1327 if (AndValue->getActiveBits() > *ShiftingValue)
1328 return;
1329
1330 auto Diag = diag(Loc: BinaryAndExpr->getOperatorLoc(),
1331 Description: "ineffective bitwise and operation");
1332 }
1333
1334 // Check for the following bound expressions:
1335 // - "binop-const-compare-to-sym",
1336 // - "binop-const-compare-to-binop-const",
1337 // Produced message:
1338 // -> "logical expression is always false/true"
1339 checkArithmeticExpr(Result);
1340
1341 // Check for the following bound expression:
1342 // - "binop-const-compare-to-const",
1343 // - "ineffective-bitwise"
1344 // Produced message:
1345 // -> "logical expression is always false/true"
1346 // -> "expression always evaluates to ..."
1347 checkBitwiseExpr(Result);
1348
1349 // Check for te following bound expression:
1350 // - "comparisons-of-symbol-and-const",
1351 // Produced messages:
1352 // -> "equivalent expression on both sides of logical operator",
1353 // -> "logical expression is always false/true"
1354 // -> "expression is redundant"
1355 checkRelationalExpr(Result);
1356}
1357
1358} // namespace clang::tidy::misc
1359

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