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 449 llvm::APInt I1 = IntLit1->getValue(); 450 llvm::APInt I2 = IntLit2->getValue(); 451 if (I1.getBitWidth() != I2.getBitWidth()) 452 return false; 453 return I1 == I2; 454 } 455 case Stmt::FloatingLiteralClass: { 456 const FloatingLiteral *FloatLit1 = cast<FloatingLiteral>(Stmt1); 457 const FloatingLiteral *FloatLit2 = cast<FloatingLiteral>(Stmt2); 458 return FloatLit1->getValue().bitwiseIsEqual(FloatLit2->getValue()); 459 } 460 case Stmt::StringLiteralClass: { 461 const StringLiteral *StringLit1 = cast<StringLiteral>(Stmt1); 462 const StringLiteral *StringLit2 = cast<StringLiteral>(Stmt2); 463 return StringLit1->getBytes() == StringLit2->getBytes(); 464 } 465 case Stmt::MemberExprClass: { 466 const MemberExpr *MemberStmt1 = cast<MemberExpr>(Stmt1); 467 const MemberExpr *MemberStmt2 = cast<MemberExpr>(Stmt2); 468 return MemberStmt1->getMemberDecl() == MemberStmt2->getMemberDecl(); 469 } 470 case Stmt::UnaryOperatorClass: { 471 const UnaryOperator *UnaryOp1 = cast<UnaryOperator>(Stmt1); 472 const UnaryOperator *UnaryOp2 = cast<UnaryOperator>(Stmt2); 473 return UnaryOp1->getOpcode() == UnaryOp2->getOpcode(); 474 } 475 } 476} 477 478//===----------------------------------------------------------------------===// 479// FindIdenticalExprChecker 480//===----------------------------------------------------------------------===// 481 482namespace { 483class FindIdenticalExprChecker : public Checker<check::ASTCodeBody> { 484public: 485 void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr, 486 BugReporter &BR) const { 487 FindIdenticalExprVisitor Visitor(BR, this, Mgr.getAnalysisDeclContext(D)); 488 Visitor.TraverseDecl(const_cast<Decl *>(D)); 489 } 490}; 491} // end anonymous namespace 492 493void ento::registerIdenticalExprChecker(CheckerManager &Mgr) { 494 Mgr.registerChecker<FindIdenticalExprChecker>(); 495} 496