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