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(B, BR.getSourceManager());
71  BR.EmitBasicReport(AC->getDecl(), Checker,
72                     "Use of identical expressions",
73                     categories::LogicError,
74                     Message, ELoc, 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>(LHS)) {
89    if (B->getOpcode() != B2->getOpcode())
90      break;
91    if (isIdenticalStmt(AC->getASTContext(), RHS, 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(AC->getASTContext(), RHS, 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>(Stmt1)) {
116    if (!CS->body_empty()) {
117      const IfStmt *InnerIf = dyn_cast<IfStmt>(*CS->body_begin());
118      if (InnerIf && isIdenticalStmt(AC->getASTContext(), I->getCond(), InnerIf->getCond(), /*IgnoreSideEffects=*/ false)) {
119        PathDiagnosticLocation ELoc(InnerIf->getCond(), BR.getSourceManager(), AC);
120        BR.EmitBasicReport(AC->getDecl(), Checker, "Identical conditions",
121          categories::LogicError,
122          "conditions of the inner and outer statements are identical",
123          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>(Else)) {
139      const Expr *Cond2 = I2->getCond();
140      if (isIdenticalStmt(AC->getASTContext(), Cond1, Cond2, false)) {
141        SourceRange Sr = Cond1->getSourceRange();
142        PathDiagnosticLocation ELoc(Cond2, BR.getSourceManager(), AC);
143        BR.EmitBasicReport(AC->getDecl(), Checker, "Identical conditions",
144                           categories::LogicError,
145                           "expression is identical to previous condition",
146                           ELoc, 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>(Stmt1)) {
162    if (CompStmt->size() == 1)
163      Stmt1 = CompStmt->body_back();
164  }
165  if (const CompoundStmt *CompStmt = dyn_cast<CompoundStmt>(Stmt2)) {
166    if (CompStmt->size() == 1)
167      Stmt2 = CompStmt->body_back();
168  }
169
170  if (isIdenticalStmt(AC->getASTContext(), Stmt1, Stmt2, true)) {
171      PathDiagnosticLocation ELoc =
172          PathDiagnosticLocation::createBegin(I, BR.getSourceManager(), AC);
173      BR.EmitBasicReport(AC->getDecl(), Checker,
174                         "Identical branches",
175                         categories::LogicError,
176                         "true and false branches are identical", ELoc);
177  }
178  return true;
179}
180
181bool FindIdenticalExprVisitor::VisitBinaryOperator(const BinaryOperator *B) {
182  BinaryOperator::Opcode Op = B->getOpcode();
183
184  if (BinaryOperator::isBitwiseOp(Op))
185    checkBitwiseOrLogicalOp(B, true);
186
187  if (BinaryOperator::isLogicalOp(Op))
188    checkBitwiseOrLogicalOp(B, false);
189
190  if (BinaryOperator::isComparisonOp(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>(LHS);
226  const DeclRefExpr *DeclRef2 = dyn_cast<DeclRefExpr>(RHS);
227  const FloatingLiteral *FloatLit1 = dyn_cast<FloatingLiteral>(LHS);
228  const FloatingLiteral *FloatLit2 = dyn_cast<FloatingLiteral>(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(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(AC->getASTContext(), B->getLHS(), B->getRHS())) {
254    PathDiagnosticLocation ELoc =
255        PathDiagnosticLocation::createOperatorLoc(B, 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(AC->getDecl(), Checker,
265                       "Compare of identical expressions",
266                       categories::LogicError, Message, 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(AC->getASTContext(), C->getTrueExpr(),
277                      C->getFalseExpr(), true)) {
278    PathDiagnosticLocation ELoc =
279        PathDiagnosticLocation::createConditionalColonLoc(
280            C, BR.getSourceManager());
281
282    SourceRange Sr[2];
283    Sr[0] = C->getTrueExpr()->getSourceRange();
284    Sr[1] = C->getFalseExpr()->getSourceRange();
285    BR.EmitBasicReport(
286        AC->getDecl(), Checker,
287        "Identical expressions in conditional expression",
288        categories::LogicError,
289        "identical expressions on both sides of ':' in conditional expression",
290        ELoc, 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>(Stmt1);
319  const Expr *Expr2 = dyn_cast<Expr>(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, *I1, *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::OMPArraySectionExprClass:
354  case Stmt::ImplicitCastExprClass:
355  case Stmt::ParenExprClass:
356  case Stmt::BreakStmtClass:
357  case Stmt::ContinueStmtClass:
358  case Stmt::NullStmtClass:
359    return true;
360  case Stmt::CStyleCastExprClass: {
361    const CStyleCastExpr* CastExpr1 = cast<CStyleCastExpr>(Stmt1);
362    const CStyleCastExpr* CastExpr2 = cast<CStyleCastExpr>(Stmt2);
363
364    return CastExpr1->getTypeAsWritten() == CastExpr2->getTypeAsWritten();
365  }
366  case Stmt::ReturnStmtClass: {
367    const ReturnStmt *ReturnStmt1 = cast<ReturnStmt>(Stmt1);
368    const ReturnStmt *ReturnStmt2 = cast<ReturnStmt>(Stmt2);
369
370    return isIdenticalStmt(Ctx, ReturnStmt1->getRetValue(),
371                           ReturnStmt2->getRetValue(), IgnoreSideEffects);
372  }
373  case Stmt::ForStmtClass: {
374    const ForStmt *ForStmt1 = cast<ForStmt>(Stmt1);
375    const ForStmt *ForStmt2 = cast<ForStmt>(Stmt2);
376
377    if (!isIdenticalStmt(Ctx, ForStmt1->getInit(), ForStmt2->getInit(),
378                         IgnoreSideEffects))
379      return false;
380    if (!isIdenticalStmt(Ctx, ForStmt1->getCond(), ForStmt2->getCond(),
381                         IgnoreSideEffects))
382      return false;
383    if (!isIdenticalStmt(Ctx, ForStmt1->getInc(), ForStmt2->getInc(),
384                         IgnoreSideEffects))
385      return false;
386    if (!isIdenticalStmt(Ctx, ForStmt1->getBody(), ForStmt2->getBody(),
387                         IgnoreSideEffects))
388      return false;
389    return true;
390  }
391  case Stmt::DoStmtClass: {
392    const DoStmt *DStmt1 = cast<DoStmt>(Stmt1);
393    const DoStmt *DStmt2 = cast<DoStmt>(Stmt2);
394
395    if (!isIdenticalStmt(Ctx, DStmt1->getCond(), DStmt2->getCond(),
396                         IgnoreSideEffects))
397      return false;
398    if (!isIdenticalStmt(Ctx, DStmt1->getBody(), DStmt2->getBody(),
399                         IgnoreSideEffects))
400      return false;
401    return true;
402  }
403  case Stmt::WhileStmtClass: {
404    const WhileStmt *WStmt1 = cast<WhileStmt>(Stmt1);
405    const WhileStmt *WStmt2 = cast<WhileStmt>(Stmt2);
406
407    if (!isIdenticalStmt(Ctx, WStmt1->getCond(), WStmt2->getCond(),
408                         IgnoreSideEffects))
409      return false;
410    if (!isIdenticalStmt(Ctx, WStmt1->getBody(), WStmt2->getBody(),
411                         IgnoreSideEffects))
412      return false;
413    return true;
414  }
415  case Stmt::IfStmtClass: {
416    const IfStmt *IStmt1 = cast<IfStmt>(Stmt1);
417    const IfStmt *IStmt2 = cast<IfStmt>(Stmt2);
418
419    if (!isIdenticalStmt(Ctx, IStmt1->getCond(), IStmt2->getCond(),
420                         IgnoreSideEffects))
421      return false;
422    if (!isIdenticalStmt(Ctx, IStmt1->getThen(), IStmt2->getThen(),
423                         IgnoreSideEffects))
424      return false;
425    if (!isIdenticalStmt(Ctx, IStmt1->getElse(), IStmt2->getElse(),
426                         IgnoreSideEffects))
427      return false;
428    return true;
429  }
430  case Stmt::CompoundStmtClass: {
431    const CompoundStmt *CompStmt1 = cast<CompoundStmt>(Stmt1);
432    const CompoundStmt *CompStmt2 = cast<CompoundStmt>(Stmt2);
433
434    if (CompStmt1->size() != CompStmt2->size())
435      return false;
436
437    CompoundStmt::const_body_iterator I1 = CompStmt1->body_begin();
438    CompoundStmt::const_body_iterator I2 = CompStmt2->body_begin();
439    while (I1 != CompStmt1->body_end() && I2 != CompStmt2->body_end()) {
440      if (!isIdenticalStmt(Ctx, *I1, *I2, IgnoreSideEffects))
441        return false;
442      ++I1;
443      ++I2;
444    }
445
446    return true;
447  }
448  case Stmt::CompoundAssignOperatorClass:
449  case Stmt::BinaryOperatorClass: {
450    const BinaryOperator *BinOp1 = cast<BinaryOperator>(Stmt1);
451    const BinaryOperator *BinOp2 = cast<BinaryOperator>(Stmt2);
452    return BinOp1->getOpcode() == BinOp2->getOpcode();
453  }
454  case Stmt::CharacterLiteralClass: {
455    const CharacterLiteral *CharLit1 = cast<CharacterLiteral>(Stmt1);
456    const CharacterLiteral *CharLit2 = cast<CharacterLiteral>(Stmt2);
457    return CharLit1->getValue() == CharLit2->getValue();
458  }
459  case Stmt::DeclRefExprClass: {
460    const DeclRefExpr *DeclRef1 = cast<DeclRefExpr>(Stmt1);
461    const DeclRefExpr *DeclRef2 = cast<DeclRefExpr>(Stmt2);
462    return DeclRef1->getDecl() == DeclRef2->getDecl();
463  }
464  case Stmt::IntegerLiteralClass: {
465    const IntegerLiteral *IntLit1 = cast<IntegerLiteral>(Stmt1);
466    const IntegerLiteral *IntLit2 = cast<IntegerLiteral>(Stmt2);
467
468    llvm::APInt I1 = IntLit1->getValue();
469    llvm::APInt I2 = IntLit2->getValue();
470    if (I1.getBitWidth() != I2.getBitWidth())
471      return false;
472    return  I1 == I2;
473  }
474  case Stmt::FloatingLiteralClass: {
475    const FloatingLiteral *FloatLit1 = cast<FloatingLiteral>(Stmt1);
476    const FloatingLiteral *FloatLit2 = cast<FloatingLiteral>(Stmt2);
477    return FloatLit1->getValue().bitwiseIsEqual(FloatLit2->getValue());
478  }
479  case Stmt::StringLiteralClass: {
480    const StringLiteral *StringLit1 = cast<StringLiteral>(Stmt1);
481    const StringLiteral *StringLit2 = cast<StringLiteral>(Stmt2);
482    return StringLit1->getBytes() == StringLit2->getBytes();
483  }
484  case Stmt::MemberExprClass: {
485    const MemberExpr *MemberStmt1 = cast<MemberExpr>(Stmt1);
486    const MemberExpr *MemberStmt2 = cast<MemberExpr>(Stmt2);
487    return MemberStmt1->getMemberDecl() == MemberStmt2->getMemberDecl();
488  }
489  case Stmt::UnaryOperatorClass: {
490    const UnaryOperator *UnaryOp1 = cast<UnaryOperator>(Stmt1);
491    const UnaryOperator *UnaryOp2 = cast<UnaryOperator>(Stmt2);
492    return UnaryOp1->getOpcode() == UnaryOp2->getOpcode();
493  }
494  }
495}
496
497//===----------------------------------------------------------------------===//
498// FindIdenticalExprChecker
499//===----------------------------------------------------------------------===//
500
501namespace {
502class FindIdenticalExprChecker : public Checker<check::ASTCodeBody> {
503public:
504  void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr,
505                        BugReporter &BR) const {
506    FindIdenticalExprVisitor Visitor(BR, this, Mgr.getAnalysisDeclContext(D));
507    Visitor.TraverseDecl(const_cast<Decl *>(D));
508  }
509};
510} // end anonymous namespace
511
512void ento::registerIdenticalExprChecker(CheckerManager &Mgr) {
513  Mgr.registerChecker<FindIdenticalExprChecker>();
514}
515
516bool ento::shouldRegisterIdenticalExprChecker(const LangOptions &LO) {
517  return true;
518}
519