1//== IdenticalExprChecker.cpp - Identical expression checker----------------==//
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/// \file
10/// This defines IdenticalExprChecker, a check that warns about
11/// unintended use of identical expressions.
12///
13/// It checks for use of identical expressions with comparison operators and
14/// inside conditional expressions.
15///
16//===----------------------------------------------------------------------===//
17
18#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
19#include "clang/AST/RecursiveASTVisitor.h"
20#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
21#include "clang/StaticAnalyzer/Core/Checker.h"
22#include "clang/StaticAnalyzer/Core/CheckerManager.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
24
25using namespace clang;
26using namespace ento;
27
28static bool isIdenticalStmt(const ASTContext &Ctx, const Stmt *Stmt1,
29 const Stmt *Stmt2, bool IgnoreSideEffects = false);
30//===----------------------------------------------------------------------===//
31// FindIdenticalExprVisitor - Identify nodes using identical expressions.
32//===----------------------------------------------------------------------===//
33
34namespace {
35class FindIdenticalExprVisitor
36 : public RecursiveASTVisitor<FindIdenticalExprVisitor> {
37 BugReporter &BR;
38 const CheckerBase *Checker;
39 AnalysisDeclContext *AC;
40public:
41 explicit FindIdenticalExprVisitor(BugReporter &B,
42 const CheckerBase *Checker,
43 AnalysisDeclContext *A)
44 : BR(B), Checker(Checker), AC(A) {}
45 // FindIdenticalExprVisitor only visits nodes
46 // that are binary operators, if statements or
47 // conditional operators.
48 bool VisitBinaryOperator(const BinaryOperator *B);
49 bool VisitIfStmt(const IfStmt *I);
50 bool VisitConditionalOperator(const ConditionalOperator *C);
51
52private:
53 void reportIdenticalExpr(const BinaryOperator *B, bool CheckBitwise,
54 ArrayRef<SourceRange> Sr);
55 void checkBitwiseOrLogicalOp(const BinaryOperator *B, bool CheckBitwise);
56 void checkComparisonOp(const BinaryOperator *B);
57};
58} // end anonymous namespace
59
60void FindIdenticalExprVisitor::reportIdenticalExpr(const BinaryOperator *B,
61 bool CheckBitwise,
62 ArrayRef<SourceRange> Sr) {
63 StringRef Message;
64 if (CheckBitwise)
65 Message = "identical expressions on both sides of bitwise operator";
66 else
67 Message = "identical expressions on both sides of logical operator";
68
69 PathDiagnosticLocation ELoc =
70 PathDiagnosticLocation::createOperatorLoc(BO: B, SM: BR.getSourceManager());
71 BR.EmitBasicReport(DeclWithIssue: AC->getDecl(), Checker,
72 BugName: "Use of identical expressions",
73 BugCategory: categories::LogicError,
74 BugStr: Message, Loc: ELoc, Ranges: Sr);
75}
76
77void FindIdenticalExprVisitor::checkBitwiseOrLogicalOp(const BinaryOperator *B,
78 bool CheckBitwise) {
79 SourceRange Sr[2];
80
81 const Expr *LHS = B->getLHS();
82 const Expr *RHS = B->getRHS();
83
84 // Split operators as long as we still have operators to split on. We will
85 // get called for every binary operator in an expression so there is no need
86 // to check every one against each other here, just the right most one with
87 // the others.
88 while (const BinaryOperator *B2 = dyn_cast<BinaryOperator>(Val: LHS)) {
89 if (B->getOpcode() != B2->getOpcode())
90 break;
91 if (isIdenticalStmt(Ctx: AC->getASTContext(), Stmt1: RHS, Stmt2: B2->getRHS())) {
92 Sr[0] = RHS->getSourceRange();
93 Sr[1] = B2->getRHS()->getSourceRange();
94 reportIdenticalExpr(B, CheckBitwise, Sr);
95 }
96 LHS = B2->getLHS();
97 }
98
99 if (isIdenticalStmt(Ctx: AC->getASTContext(), Stmt1: RHS, Stmt2: LHS)) {
100 Sr[0] = RHS->getSourceRange();
101 Sr[1] = LHS->getSourceRange();
102 reportIdenticalExpr(B, CheckBitwise, Sr);
103 }
104}
105
106bool FindIdenticalExprVisitor::VisitIfStmt(const IfStmt *I) {
107 const Stmt *Stmt1 = I->getThen();
108 const Stmt *Stmt2 = I->getElse();
109
110 // Check for identical inner condition:
111 //
112 // if (x<10) {
113 // if (x<10) {
114 // ..
115 if (const CompoundStmt *CS = dyn_cast<CompoundStmt>(Val: Stmt1)) {
116 if (!CS->body_empty()) {
117 const IfStmt *InnerIf = dyn_cast<IfStmt>(Val: *CS->body_begin());
118 if (InnerIf && isIdenticalStmt(Ctx: AC->getASTContext(), Stmt1: I->getCond(), Stmt2: InnerIf->getCond(), /*IgnoreSideEffects=*/ false)) {
119 PathDiagnosticLocation ELoc(InnerIf->getCond(), BR.getSourceManager(), AC);
120 BR.EmitBasicReport(DeclWithIssue: AC->getDecl(), Checker, BugName: "Identical conditions",
121 BugCategory: categories::LogicError,
122 BugStr: "conditions of the inner and outer statements are identical",
123 Loc: ELoc);
124 }
125 }
126 }
127
128 // Check for identical conditions:
129 //
130 // if (b) {
131 // foo1();
132 // } else if (b) {
133 // foo2();
134 // }
135 if (Stmt1 && Stmt2) {
136 const Expr *Cond1 = I->getCond();
137 const Stmt *Else = Stmt2;
138 while (const IfStmt *I2 = dyn_cast_or_null<IfStmt>(Val: Else)) {
139 const Expr *Cond2 = I2->getCond();
140 if (isIdenticalStmt(Ctx: AC->getASTContext(), Stmt1: Cond1, Stmt2: Cond2, IgnoreSideEffects: false)) {
141 SourceRange Sr = Cond1->getSourceRange();
142 PathDiagnosticLocation ELoc(Cond2, BR.getSourceManager(), AC);
143 BR.EmitBasicReport(DeclWithIssue: AC->getDecl(), Checker, BugName: "Identical conditions",
144 BugCategory: categories::LogicError,
145 BugStr: "expression is identical to previous condition",
146 Loc: ELoc, Ranges: Sr);
147 }
148 Else = I2->getElse();
149 }
150 }
151
152 if (!Stmt1 || !Stmt2)
153 return true;
154
155 // Special handling for code like:
156 //
157 // if (b) {
158 // i = 1;
159 // } else
160 // i = 1;
161 if (const CompoundStmt *CompStmt = dyn_cast<CompoundStmt>(Val: Stmt1)) {
162 if (CompStmt->size() == 1)
163 Stmt1 = CompStmt->body_back();
164 }
165 if (const CompoundStmt *CompStmt = dyn_cast<CompoundStmt>(Val: Stmt2)) {
166 if (CompStmt->size() == 1)
167 Stmt2 = CompStmt->body_back();
168 }
169
170 if (isIdenticalStmt(Ctx: AC->getASTContext(), Stmt1, Stmt2, IgnoreSideEffects: true)) {
171 PathDiagnosticLocation ELoc =
172 PathDiagnosticLocation::createBegin(S: I, SM: BR.getSourceManager(), LAC: AC);
173 BR.EmitBasicReport(DeclWithIssue: AC->getDecl(), Checker,
174 BugName: "Identical branches",
175 BugCategory: categories::LogicError,
176 BugStr: "true and false branches are identical", Loc: ELoc);
177 }
178 return true;
179}
180
181bool FindIdenticalExprVisitor::VisitBinaryOperator(const BinaryOperator *B) {
182 BinaryOperator::Opcode Op = B->getOpcode();
183
184 if (BinaryOperator::isBitwiseOp(Opc: Op))
185 checkBitwiseOrLogicalOp(B, CheckBitwise: true);
186
187 if (BinaryOperator::isLogicalOp(Opc: Op))
188 checkBitwiseOrLogicalOp(B, CheckBitwise: false);
189
190 if (BinaryOperator::isComparisonOp(Opc: Op))
191 checkComparisonOp(B);
192
193 // We want to visit ALL nodes (subexpressions of binary comparison
194 // expressions too) that contains comparison operators.
195 // True is always returned to traverse ALL nodes.
196 return true;
197}
198
199void FindIdenticalExprVisitor::checkComparisonOp(const BinaryOperator *B) {
200 BinaryOperator::Opcode Op = B->getOpcode();
201
202 //
203 // Special case for floating-point representation.
204 //
205 // If expressions on both sides of comparison operator are of type float,
206 // then for some comparison operators no warning shall be
207 // reported even if the expressions are identical from a symbolic point of
208 // view. Comparison between expressions, declared variables and literals
209 // are treated differently.
210 //
211 // != and == between float literals that have the same value should NOT warn.
212 // < > between float literals that have the same value SHOULD warn.
213 //
214 // != and == between the same float declaration should NOT warn.
215 // < > between the same float declaration SHOULD warn.
216 //
217 // != and == between eq. expressions that evaluates into float
218 // should NOT warn.
219 // < > between eq. expressions that evaluates into float
220 // should NOT warn.
221 //
222 const Expr *LHS = B->getLHS()->IgnoreParenImpCasts();
223 const Expr *RHS = B->getRHS()->IgnoreParenImpCasts();
224
225 const DeclRefExpr *DeclRef1 = dyn_cast<DeclRefExpr>(Val: LHS);
226 const DeclRefExpr *DeclRef2 = dyn_cast<DeclRefExpr>(Val: RHS);
227 const FloatingLiteral *FloatLit1 = dyn_cast<FloatingLiteral>(Val: LHS);
228 const FloatingLiteral *FloatLit2 = dyn_cast<FloatingLiteral>(Val: RHS);
229 if ((DeclRef1) && (DeclRef2)) {
230 if ((DeclRef1->getType()->hasFloatingRepresentation()) &&
231 (DeclRef2->getType()->hasFloatingRepresentation())) {
232 if (DeclRef1->getDecl() == DeclRef2->getDecl()) {
233 if ((Op == BO_EQ) || (Op == BO_NE)) {
234 return;
235 }
236 }
237 }
238 } else if ((FloatLit1) && (FloatLit2)) {
239 if (FloatLit1->getValue().bitwiseIsEqual(RHS: FloatLit2->getValue())) {
240 if ((Op == BO_EQ) || (Op == BO_NE)) {
241 return;
242 }
243 }
244 } else if (LHS->getType()->hasFloatingRepresentation()) {
245 // If any side of comparison operator still has floating-point
246 // representation, then it's an expression. Don't warn.
247 // Here only LHS is checked since RHS will be implicit casted to float.
248 return;
249 } else {
250 // No special case with floating-point representation, report as usual.
251 }
252
253 if (isIdenticalStmt(Ctx: AC->getASTContext(), Stmt1: B->getLHS(), Stmt2: B->getRHS())) {
254 PathDiagnosticLocation ELoc =
255 PathDiagnosticLocation::createOperatorLoc(BO: B, SM: BR.getSourceManager());
256 StringRef Message;
257 if (Op == BO_Cmp)
258 Message = "comparison of identical expressions always evaluates to "
259 "'equal'";
260 else if (((Op == BO_EQ) || (Op == BO_LE) || (Op == BO_GE)))
261 Message = "comparison of identical expressions always evaluates to true";
262 else
263 Message = "comparison of identical expressions always evaluates to false";
264 BR.EmitBasicReport(DeclWithIssue: AC->getDecl(), Checker,
265 BugName: "Compare of identical expressions",
266 BugCategory: categories::LogicError, BugStr: Message, Loc: ELoc);
267 }
268}
269
270bool FindIdenticalExprVisitor::VisitConditionalOperator(
271 const ConditionalOperator *C) {
272
273 // Check if expressions in conditional expression are identical
274 // from a symbolic point of view.
275
276 if (isIdenticalStmt(Ctx: AC->getASTContext(), Stmt1: C->getTrueExpr(),
277 Stmt2: C->getFalseExpr(), IgnoreSideEffects: true)) {
278 PathDiagnosticLocation ELoc =
279 PathDiagnosticLocation::createConditionalColonLoc(
280 CO: C, SM: BR.getSourceManager());
281
282 SourceRange Sr[2];
283 Sr[0] = C->getTrueExpr()->getSourceRange();
284 Sr[1] = C->getFalseExpr()->getSourceRange();
285 BR.EmitBasicReport(
286 DeclWithIssue: AC->getDecl(), Checker,
287 BugName: "Identical expressions in conditional expression",
288 BugCategory: categories::LogicError,
289 BugStr: "identical expressions on both sides of ':' in conditional expression",
290 Loc: ELoc, Ranges: Sr);
291 }
292 // We want to visit ALL nodes (expressions in conditional
293 // expressions too) that contains conditional operators,
294 // thus always return true to traverse ALL nodes.
295 return true;
296}
297
298/// Determines whether two statement trees are identical regarding
299/// operators and symbols.
300///
301/// Exceptions: expressions containing macros or functions with possible side
302/// effects are never considered identical.
303/// Limitations: (t + u) and (u + t) are not considered identical.
304/// t*(u + t) and t*u + t*t are not considered identical.
305///
306static bool isIdenticalStmt(const ASTContext &Ctx, const Stmt *Stmt1,
307 const Stmt *Stmt2, bool IgnoreSideEffects) {
308
309 if (!Stmt1 || !Stmt2) {
310 return !Stmt1 && !Stmt2;
311 }
312
313 // If Stmt1 & Stmt2 are of different class then they are not
314 // identical statements.
315 if (Stmt1->getStmtClass() != Stmt2->getStmtClass())
316 return false;
317
318 const Expr *Expr1 = dyn_cast<Expr>(Val: Stmt1);
319 const Expr *Expr2 = dyn_cast<Expr>(Val: Stmt2);
320
321 if (Expr1 && Expr2) {
322 // If Stmt1 has side effects then don't warn even if expressions
323 // are identical.
324 if (!IgnoreSideEffects && Expr1->HasSideEffects(Ctx))
325 return false;
326 // If either expression comes from a macro then don't warn even if
327 // the expressions are identical.
328 if ((Expr1->getExprLoc().isMacroID()) || (Expr2->getExprLoc().isMacroID()))
329 return false;
330
331 // If all children of two expressions are identical, return true.
332 Expr::const_child_iterator I1 = Expr1->child_begin();
333 Expr::const_child_iterator I2 = Expr2->child_begin();
334 while (I1 != Expr1->child_end() && I2 != Expr2->child_end()) {
335 if (!*I1 || !*I2 || !isIdenticalStmt(Ctx, Stmt1: *I1, Stmt2: *I2, IgnoreSideEffects))
336 return false;
337 ++I1;
338 ++I2;
339 }
340 // If there are different number of children in the statements, return
341 // false.
342 if (I1 != Expr1->child_end())
343 return false;
344 if (I2 != Expr2->child_end())
345 return false;
346 }
347
348 switch (Stmt1->getStmtClass()) {
349 default:
350 return false;
351 case Stmt::CallExprClass:
352 case Stmt::ArraySubscriptExprClass:
353 case Stmt::ArraySectionExprClass:
354 case Stmt::OMPArrayShapingExprClass:
355 case Stmt::OMPIteratorExprClass:
356 case Stmt::ImplicitCastExprClass:
357 case Stmt::ParenExprClass:
358 case Stmt::BreakStmtClass:
359 case Stmt::ContinueStmtClass:
360 case Stmt::NullStmtClass:
361 return true;
362 case Stmt::CStyleCastExprClass: {
363 const CStyleCastExpr* CastExpr1 = cast<CStyleCastExpr>(Val: Stmt1);
364 const CStyleCastExpr* CastExpr2 = cast<CStyleCastExpr>(Val: Stmt2);
365
366 return CastExpr1->getTypeAsWritten() == CastExpr2->getTypeAsWritten();
367 }
368 case Stmt::ReturnStmtClass: {
369 const ReturnStmt *ReturnStmt1 = cast<ReturnStmt>(Val: Stmt1);
370 const ReturnStmt *ReturnStmt2 = cast<ReturnStmt>(Val: Stmt2);
371
372 return isIdenticalStmt(Ctx, Stmt1: ReturnStmt1->getRetValue(),
373 Stmt2: ReturnStmt2->getRetValue(), IgnoreSideEffects);
374 }
375 case Stmt::ForStmtClass: {
376 const ForStmt *ForStmt1 = cast<ForStmt>(Val: Stmt1);
377 const ForStmt *ForStmt2 = cast<ForStmt>(Val: Stmt2);
378
379 if (!isIdenticalStmt(Ctx, Stmt1: ForStmt1->getInit(), Stmt2: ForStmt2->getInit(),
380 IgnoreSideEffects))
381 return false;
382 if (!isIdenticalStmt(Ctx, Stmt1: ForStmt1->getCond(), Stmt2: ForStmt2->getCond(),
383 IgnoreSideEffects))
384 return false;
385 if (!isIdenticalStmt(Ctx, Stmt1: ForStmt1->getInc(), Stmt2: ForStmt2->getInc(),
386 IgnoreSideEffects))
387 return false;
388 if (!isIdenticalStmt(Ctx, Stmt1: ForStmt1->getBody(), Stmt2: ForStmt2->getBody(),
389 IgnoreSideEffects))
390 return false;
391 return true;
392 }
393 case Stmt::DoStmtClass: {
394 const DoStmt *DStmt1 = cast<DoStmt>(Val: Stmt1);
395 const DoStmt *DStmt2 = cast<DoStmt>(Val: Stmt2);
396
397 if (!isIdenticalStmt(Ctx, Stmt1: DStmt1->getCond(), Stmt2: DStmt2->getCond(),
398 IgnoreSideEffects))
399 return false;
400 if (!isIdenticalStmt(Ctx, Stmt1: DStmt1->getBody(), Stmt2: DStmt2->getBody(),
401 IgnoreSideEffects))
402 return false;
403 return true;
404 }
405 case Stmt::WhileStmtClass: {
406 const WhileStmt *WStmt1 = cast<WhileStmt>(Val: Stmt1);
407 const WhileStmt *WStmt2 = cast<WhileStmt>(Val: Stmt2);
408
409 if (!isIdenticalStmt(Ctx, Stmt1: WStmt1->getCond(), Stmt2: WStmt2->getCond(),
410 IgnoreSideEffects))
411 return false;
412 if (!isIdenticalStmt(Ctx, Stmt1: WStmt1->getBody(), Stmt2: WStmt2->getBody(),
413 IgnoreSideEffects))
414 return false;
415 return true;
416 }
417 case Stmt::IfStmtClass: {
418 const IfStmt *IStmt1 = cast<IfStmt>(Val: Stmt1);
419 const IfStmt *IStmt2 = cast<IfStmt>(Val: Stmt2);
420
421 if (!isIdenticalStmt(Ctx, Stmt1: IStmt1->getCond(), Stmt2: IStmt2->getCond(),
422 IgnoreSideEffects))
423 return false;
424 if (!isIdenticalStmt(Ctx, Stmt1: IStmt1->getThen(), Stmt2: IStmt2->getThen(),
425 IgnoreSideEffects))
426 return false;
427 if (!isIdenticalStmt(Ctx, Stmt1: IStmt1->getElse(), Stmt2: IStmt2->getElse(),
428 IgnoreSideEffects))
429 return false;
430 return true;
431 }
432 case Stmt::CompoundStmtClass: {
433 const CompoundStmt *CompStmt1 = cast<CompoundStmt>(Val: Stmt1);
434 const CompoundStmt *CompStmt2 = cast<CompoundStmt>(Val: Stmt2);
435
436 if (CompStmt1->size() != CompStmt2->size())
437 return false;
438
439 CompoundStmt::const_body_iterator I1 = CompStmt1->body_begin();
440 CompoundStmt::const_body_iterator I2 = CompStmt2->body_begin();
441 while (I1 != CompStmt1->body_end() && I2 != CompStmt2->body_end()) {
442 if (!isIdenticalStmt(Ctx, Stmt1: *I1, Stmt2: *I2, IgnoreSideEffects))
443 return false;
444 ++I1;
445 ++I2;
446 }
447
448 return true;
449 }
450 case Stmt::CompoundAssignOperatorClass:
451 case Stmt::BinaryOperatorClass: {
452 const BinaryOperator *BinOp1 = cast<BinaryOperator>(Val: Stmt1);
453 const BinaryOperator *BinOp2 = cast<BinaryOperator>(Val: Stmt2);
454 return BinOp1->getOpcode() == BinOp2->getOpcode();
455 }
456 case Stmt::CharacterLiteralClass: {
457 const CharacterLiteral *CharLit1 = cast<CharacterLiteral>(Val: Stmt1);
458 const CharacterLiteral *CharLit2 = cast<CharacterLiteral>(Val: Stmt2);
459 return CharLit1->getValue() == CharLit2->getValue();
460 }
461 case Stmt::DeclRefExprClass: {
462 const DeclRefExpr *DeclRef1 = cast<DeclRefExpr>(Val: Stmt1);
463 const DeclRefExpr *DeclRef2 = cast<DeclRefExpr>(Val: Stmt2);
464 return DeclRef1->getDecl() == DeclRef2->getDecl();
465 }
466 case Stmt::IntegerLiteralClass: {
467 const IntegerLiteral *IntLit1 = cast<IntegerLiteral>(Val: Stmt1);
468 const IntegerLiteral *IntLit2 = cast<IntegerLiteral>(Val: Stmt2);
469
470 llvm::APInt I1 = IntLit1->getValue();
471 llvm::APInt I2 = IntLit2->getValue();
472 if (I1.getBitWidth() != I2.getBitWidth())
473 return false;
474 return I1 == I2;
475 }
476 case Stmt::FloatingLiteralClass: {
477 const FloatingLiteral *FloatLit1 = cast<FloatingLiteral>(Val: Stmt1);
478 const FloatingLiteral *FloatLit2 = cast<FloatingLiteral>(Val: Stmt2);
479 return FloatLit1->getValue().bitwiseIsEqual(RHS: FloatLit2->getValue());
480 }
481 case Stmt::StringLiteralClass: {
482 const StringLiteral *StringLit1 = cast<StringLiteral>(Val: Stmt1);
483 const StringLiteral *StringLit2 = cast<StringLiteral>(Val: Stmt2);
484 return StringLit1->getBytes() == StringLit2->getBytes();
485 }
486 case Stmt::MemberExprClass: {
487 const MemberExpr *MemberStmt1 = cast<MemberExpr>(Val: Stmt1);
488 const MemberExpr *MemberStmt2 = cast<MemberExpr>(Val: Stmt2);
489 return MemberStmt1->getMemberDecl() == MemberStmt2->getMemberDecl();
490 }
491 case Stmt::UnaryOperatorClass: {
492 const UnaryOperator *UnaryOp1 = cast<UnaryOperator>(Val: Stmt1);
493 const UnaryOperator *UnaryOp2 = cast<UnaryOperator>(Val: Stmt2);
494 return UnaryOp1->getOpcode() == UnaryOp2->getOpcode();
495 }
496 }
497}
498
499//===----------------------------------------------------------------------===//
500// FindIdenticalExprChecker
501//===----------------------------------------------------------------------===//
502
503namespace {
504class FindIdenticalExprChecker : public Checker<check::ASTCodeBody> {
505public:
506 void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr,
507 BugReporter &BR) const {
508 FindIdenticalExprVisitor Visitor(BR, this, Mgr.getAnalysisDeclContext(D));
509 Visitor.TraverseDecl(D: const_cast<Decl *>(D));
510 }
511};
512} // end anonymous namespace
513
514void ento::registerIdenticalExprChecker(CheckerManager &Mgr) {
515 Mgr.registerChecker<FindIdenticalExprChecker>();
516}
517
518bool ento::shouldRegisterIdenticalExprChecker(const CheckerManager &mgr) {
519 return true;
520}
521