BugReporter.cpp revision e172e8b9e7fc67d7d03589af7e92fe777afcf33a
1// BugReporter.cpp - Generate PathDiagnostics for Bugs ------------*- C++ -*--// 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// This file defines BugReporter, a utility class for generating 11// PathDiagnostics. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 16#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 17#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 18#include "clang/AST/ASTContext.h" 19#include "clang/Analysis/CFG.h" 20#include "clang/AST/Expr.h" 21#include "clang/AST/ParentMap.h" 22#include "clang/AST/StmtObjC.h" 23#include "clang/Basic/SourceManager.h" 24#include "clang/Analysis/ProgramPoint.h" 25#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" 26#include "llvm/Support/raw_ostream.h" 27#include "llvm/ADT/DenseMap.h" 28#include "llvm/ADT/STLExtras.h" 29#include "llvm/ADT/OwningPtr.h" 30#include <queue> 31 32using namespace clang; 33using namespace ento; 34 35BugReporterVisitor::~BugReporterVisitor() {} 36BugReporterContext::~BugReporterContext() { 37 for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I) 38 if ((*I)->isOwnedByReporterContext()) delete *I; 39} 40 41void BugReporterContext::addVisitor(BugReporterVisitor* visitor) { 42 if (!visitor) 43 return; 44 45 llvm::FoldingSetNodeID ID; 46 visitor->Profile(ID); 47 void *InsertPos; 48 49 if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) { 50 delete visitor; 51 return; 52 } 53 54 CallbacksSet.InsertNode(visitor, InsertPos); 55 Callbacks = F.add(visitor, Callbacks); 56} 57 58//===----------------------------------------------------------------------===// 59// Helper routines for walking the ExplodedGraph and fetching statements. 60//===----------------------------------------------------------------------===// 61 62static inline const Stmt *GetStmt(const ProgramPoint &P) { 63 if (const StmtPoint* SP = dyn_cast<StmtPoint>(&P)) 64 return SP->getStmt(); 65 else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) 66 return BE->getSrc()->getTerminator(); 67 68 return 0; 69} 70 71static inline const ExplodedNode* 72GetPredecessorNode(const ExplodedNode *N) { 73 return N->pred_empty() ? NULL : *(N->pred_begin()); 74} 75 76static inline const ExplodedNode* 77GetSuccessorNode(const ExplodedNode *N) { 78 return N->succ_empty() ? NULL : *(N->succ_begin()); 79} 80 81static const Stmt *GetPreviousStmt(const ExplodedNode *N) { 82 for (N = GetPredecessorNode(N); N; N = GetPredecessorNode(N)) 83 if (const Stmt *S = GetStmt(N->getLocation())) 84 return S; 85 86 return 0; 87} 88 89static const Stmt *GetNextStmt(const ExplodedNode *N) { 90 for (N = GetSuccessorNode(N); N; N = GetSuccessorNode(N)) 91 if (const Stmt *S = GetStmt(N->getLocation())) { 92 // Check if the statement is '?' or '&&'/'||'. These are "merges", 93 // not actual statement points. 94 switch (S->getStmtClass()) { 95 case Stmt::ChooseExprClass: 96 case Stmt::BinaryConditionalOperatorClass: continue; 97 case Stmt::ConditionalOperatorClass: continue; 98 case Stmt::BinaryOperatorClass: { 99 BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode(); 100 if (Op == BO_LAnd || Op == BO_LOr) 101 continue; 102 break; 103 } 104 default: 105 break; 106 } 107 108 // Some expressions don't have locations. 109 if (S->getLocStart().isInvalid()) 110 continue; 111 112 return S; 113 } 114 115 return 0; 116} 117 118static inline const Stmt* 119GetCurrentOrPreviousStmt(const ExplodedNode *N) { 120 if (const Stmt *S = GetStmt(N->getLocation())) 121 return S; 122 123 return GetPreviousStmt(N); 124} 125 126static inline const Stmt* 127GetCurrentOrNextStmt(const ExplodedNode *N) { 128 if (const Stmt *S = GetStmt(N->getLocation())) 129 return S; 130 131 return GetNextStmt(N); 132} 133 134//===----------------------------------------------------------------------===// 135// PathDiagnosticBuilder and its associated routines and helper objects. 136//===----------------------------------------------------------------------===// 137 138typedef llvm::DenseMap<const ExplodedNode*, 139const ExplodedNode*> NodeBackMap; 140 141namespace { 142class NodeMapClosure : public BugReport::NodeResolver { 143 NodeBackMap& M; 144public: 145 NodeMapClosure(NodeBackMap *m) : M(*m) {} 146 ~NodeMapClosure() {} 147 148 const ExplodedNode *getOriginalNode(const ExplodedNode *N) { 149 NodeBackMap::iterator I = M.find(N); 150 return I == M.end() ? 0 : I->second; 151 } 152}; 153 154class PathDiagnosticBuilder : public BugReporterContext { 155 BugReport *R; 156 PathDiagnosticClient *PDC; 157 llvm::OwningPtr<ParentMap> PM; 158 NodeMapClosure NMC; 159public: 160 PathDiagnosticBuilder(GRBugReporter &br, 161 BugReport *r, NodeBackMap *Backmap, 162 PathDiagnosticClient *pdc) 163 : BugReporterContext(br), 164 R(r), PDC(pdc), NMC(Backmap) { 165 addVisitor(R); 166 } 167 168 PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N); 169 170 PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os, 171 const ExplodedNode *N); 172 173 Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); } 174 175 ParentMap& getParentMap() { return R->getErrorNode()->getParentMap(); } 176 177 const Stmt *getParent(const Stmt *S) { 178 return getParentMap().getParent(S); 179 } 180 181 virtual NodeMapClosure& getNodeResolver() { return NMC; } 182 183 PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S); 184 185 PathDiagnosticClient::PathGenerationScheme getGenerationScheme() const { 186 return PDC ? PDC->getGenerationScheme() : PathDiagnosticClient::Extensive; 187 } 188 189 bool supportsLogicalOpControlFlow() const { 190 return PDC ? PDC->supportsLogicalOpControlFlow() : true; 191 } 192}; 193} // end anonymous namespace 194 195PathDiagnosticLocation 196PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) { 197 if (const Stmt *S = GetNextStmt(N)) 198 return PathDiagnosticLocation(S, getSourceManager()); 199 200 return FullSourceLoc(N->getLocationContext()->getDecl()->getBodyRBrace(), 201 getSourceManager()); 202} 203 204PathDiagnosticLocation 205PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os, 206 const ExplodedNode *N) { 207 208 // Slow, but probably doesn't matter. 209 if (os.str().empty()) 210 os << ' '; 211 212 const PathDiagnosticLocation &Loc = ExecutionContinues(N); 213 214 if (Loc.asStmt()) 215 os << "Execution continues on line " 216 << getSourceManager().getExpansionLineNumber(Loc.asLocation()) 217 << '.'; 218 else { 219 os << "Execution jumps to the end of the "; 220 const Decl *D = N->getLocationContext()->getDecl(); 221 if (isa<ObjCMethodDecl>(D)) 222 os << "method"; 223 else if (isa<FunctionDecl>(D)) 224 os << "function"; 225 else { 226 assert(isa<BlockDecl>(D)); 227 os << "anonymous block"; 228 } 229 os << '.'; 230 } 231 232 return Loc; 233} 234 235static bool IsNested(const Stmt *S, ParentMap &PM) { 236 if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S))) 237 return true; 238 239 const Stmt *Parent = PM.getParentIgnoreParens(S); 240 241 if (Parent) 242 switch (Parent->getStmtClass()) { 243 case Stmt::ForStmtClass: 244 case Stmt::DoStmtClass: 245 case Stmt::WhileStmtClass: 246 return true; 247 default: 248 break; 249 } 250 251 return false; 252} 253 254PathDiagnosticLocation 255PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { 256 assert(S && "Null Stmt *passed to getEnclosingStmtLocation"); 257 ParentMap &P = getParentMap(); 258 SourceManager &SMgr = getSourceManager(); 259 260 while (IsNested(S, P)) { 261 const Stmt *Parent = P.getParentIgnoreParens(S); 262 263 if (!Parent) 264 break; 265 266 switch (Parent->getStmtClass()) { 267 case Stmt::BinaryOperatorClass: { 268 const BinaryOperator *B = cast<BinaryOperator>(Parent); 269 if (B->isLogicalOp()) 270 return PathDiagnosticLocation(S, SMgr); 271 break; 272 } 273 case Stmt::CompoundStmtClass: 274 case Stmt::StmtExprClass: 275 return PathDiagnosticLocation(S, SMgr); 276 case Stmt::ChooseExprClass: 277 // Similar to '?' if we are referring to condition, just have the edge 278 // point to the entire choose expression. 279 if (cast<ChooseExpr>(Parent)->getCond() == S) 280 return PathDiagnosticLocation(Parent, SMgr); 281 else 282 return PathDiagnosticLocation(S, SMgr); 283 case Stmt::BinaryConditionalOperatorClass: 284 case Stmt::ConditionalOperatorClass: 285 // For '?', if we are referring to condition, just have the edge point 286 // to the entire '?' expression. 287 if (cast<AbstractConditionalOperator>(Parent)->getCond() == S) 288 return PathDiagnosticLocation(Parent, SMgr); 289 else 290 return PathDiagnosticLocation(S, SMgr); 291 case Stmt::DoStmtClass: 292 return PathDiagnosticLocation(S, SMgr); 293 case Stmt::ForStmtClass: 294 if (cast<ForStmt>(Parent)->getBody() == S) 295 return PathDiagnosticLocation(S, SMgr); 296 break; 297 case Stmt::IfStmtClass: 298 if (cast<IfStmt>(Parent)->getCond() != S) 299 return PathDiagnosticLocation(S, SMgr); 300 break; 301 case Stmt::ObjCForCollectionStmtClass: 302 if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S) 303 return PathDiagnosticLocation(S, SMgr); 304 break; 305 case Stmt::WhileStmtClass: 306 if (cast<WhileStmt>(Parent)->getCond() != S) 307 return PathDiagnosticLocation(S, SMgr); 308 break; 309 default: 310 break; 311 } 312 313 S = Parent; 314 } 315 316 assert(S && "Cannot have null Stmt for PathDiagnosticLocation"); 317 318 // Special case: DeclStmts can appear in for statement declarations, in which 319 // case the ForStmt is the context. 320 if (isa<DeclStmt>(S)) { 321 if (const Stmt *Parent = P.getParent(S)) { 322 switch (Parent->getStmtClass()) { 323 case Stmt::ForStmtClass: 324 case Stmt::ObjCForCollectionStmtClass: 325 return PathDiagnosticLocation(Parent, SMgr); 326 default: 327 break; 328 } 329 } 330 } 331 else if (isa<BinaryOperator>(S)) { 332 // Special case: the binary operator represents the initialization 333 // code in a for statement (this can happen when the variable being 334 // initialized is an old variable. 335 if (const ForStmt *FS = 336 dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) { 337 if (FS->getInit() == S) 338 return PathDiagnosticLocation(FS, SMgr); 339 } 340 } 341 342 return PathDiagnosticLocation(S, SMgr); 343} 344 345//===----------------------------------------------------------------------===// 346// ScanNotableSymbols: closure-like callback for scanning Store bindings. 347//===----------------------------------------------------------------------===// 348 349static const VarDecl* GetMostRecentVarDeclBinding(const ExplodedNode *N, 350 ProgramStateManager& VMgr, 351 SVal X) { 352 353 for ( ; N ; N = N->pred_empty() ? 0 : *N->pred_begin()) { 354 355 ProgramPoint P = N->getLocation(); 356 357 if (!isa<PostStmt>(P)) 358 continue; 359 360 const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(cast<PostStmt>(P).getStmt()); 361 362 if (!DR) 363 continue; 364 365 SVal Y = N->getState()->getSVal(DR); 366 367 if (X != Y) 368 continue; 369 370 const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()); 371 372 if (!VD) 373 continue; 374 375 return VD; 376 } 377 378 return 0; 379} 380 381namespace { 382class NotableSymbolHandler 383: public StoreManager::BindingsHandler { 384 385 SymbolRef Sym; 386 const ProgramState *PrevSt; 387 const Stmt *S; 388 ProgramStateManager& VMgr; 389 const ExplodedNode *Pred; 390 PathDiagnostic& PD; 391 BugReporter& BR; 392 393public: 394 395 NotableSymbolHandler(SymbolRef sym, 396 const ProgramState *prevst, 397 const Stmt *s, 398 ProgramStateManager& vmgr, 399 const ExplodedNode *pred, 400 PathDiagnostic& pd, 401 BugReporter& br) 402 : Sym(sym), 403 PrevSt(prevst), 404 S(s), 405 VMgr(vmgr), 406 Pred(pred), 407 PD(pd), 408 BR(br) {} 409 410 bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R, 411 SVal V) { 412 413 SymbolRef ScanSym = V.getAsSymbol(); 414 415 if (ScanSym != Sym) 416 return true; 417 418 // Check if the previous state has this binding. 419 SVal X = PrevSt->getSVal(loc::MemRegionVal(R)); 420 421 if (X == V) // Same binding? 422 return true; 423 424 // Different binding. Only handle assignments for now. We don't pull 425 // this check out of the loop because we will eventually handle other 426 // cases. 427 428 VarDecl *VD = 0; 429 430 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 431 if (!B->isAssignmentOp()) 432 return true; 433 434 // What variable did we assign to? 435 DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts()); 436 437 if (!DR) 438 return true; 439 440 VD = dyn_cast<VarDecl>(DR->getDecl()); 441 } 442 else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) { 443 // FIXME: Eventually CFGs won't have DeclStmts. Right now we 444 // assume that each DeclStmt has a single Decl. This invariant 445 // holds by construction in the CFG. 446 VD = dyn_cast<VarDecl>(*DS->decl_begin()); 447 } 448 449 if (!VD) 450 return true; 451 452 // What is the most recently referenced variable with this binding? 453 const VarDecl *MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V); 454 455 if (!MostRecent) 456 return true; 457 458 // Create the diagnostic. 459 FullSourceLoc L(S->getLocStart(), BR.getSourceManager()); 460 461 if (Loc::isLocType(VD->getType())) { 462 std::string msg = "'" + std::string(VD->getNameAsString()) + 463 "' now aliases '" + MostRecent->getNameAsString() + "'"; 464 465 PD.push_front(new PathDiagnosticEventPiece(L, msg)); 466 } 467 468 return true; 469 } 470}; 471} 472 473static void HandleNotableSymbol(const ExplodedNode *N, 474 const Stmt *S, 475 SymbolRef Sym, BugReporter& BR, 476 PathDiagnostic& PD) { 477 478 const ExplodedNode *Pred = N->pred_empty() ? 0 : *N->pred_begin(); 479 const ProgramState *PrevSt = Pred ? Pred->getState() : 0; 480 481 if (!PrevSt) 482 return; 483 484 // Look at the region bindings of the current state that map to the 485 // specified symbol. Are any of them not in the previous state? 486 ProgramStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager(); 487 NotableSymbolHandler H(Sym, PrevSt, S, VMgr, Pred, PD, BR); 488 cast<GRBugReporter>(BR).getStateManager().iterBindings(N->getState(), H); 489} 490 491namespace { 492class ScanNotableSymbols 493: public StoreManager::BindingsHandler { 494 495 llvm::SmallSet<SymbolRef, 10> AlreadyProcessed; 496 const ExplodedNode *N; 497 const Stmt *S; 498 GRBugReporter& BR; 499 PathDiagnostic& PD; 500 501public: 502 ScanNotableSymbols(const ExplodedNode *n, const Stmt *s, 503 GRBugReporter& br, PathDiagnostic& pd) 504 : N(n), S(s), BR(br), PD(pd) {} 505 506 bool HandleBinding(StoreManager& SMgr, Store store, 507 const MemRegion* R, SVal V) { 508 509 SymbolRef ScanSym = V.getAsSymbol(); 510 511 if (!ScanSym) 512 return true; 513 514 if (!BR.isNotable(ScanSym)) 515 return true; 516 517 if (AlreadyProcessed.count(ScanSym)) 518 return true; 519 520 AlreadyProcessed.insert(ScanSym); 521 522 HandleNotableSymbol(N, S, ScanSym, BR, PD); 523 return true; 524 } 525}; 526} // end anonymous namespace 527 528//===----------------------------------------------------------------------===// 529// "Minimal" path diagnostic generation algorithm. 530//===----------------------------------------------------------------------===// 531 532static void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM); 533 534static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, 535 PathDiagnosticBuilder &PDB, 536 const ExplodedNode *N) { 537 538 SourceManager& SMgr = PDB.getSourceManager(); 539 const ExplodedNode *NextNode = N->pred_empty() 540 ? NULL : *(N->pred_begin()); 541 while (NextNode) { 542 N = NextNode; 543 NextNode = GetPredecessorNode(N); 544 545 ProgramPoint P = N->getLocation(); 546 547 if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { 548 const CFGBlock *Src = BE->getSrc(); 549 const CFGBlock *Dst = BE->getDst(); 550 const Stmt *T = Src->getTerminator(); 551 552 if (!T) 553 continue; 554 555 FullSourceLoc Start(T->getLocStart(), SMgr); 556 557 switch (T->getStmtClass()) { 558 default: 559 break; 560 561 case Stmt::GotoStmtClass: 562 case Stmt::IndirectGotoStmtClass: { 563 const Stmt *S = GetNextStmt(N); 564 565 if (!S) 566 continue; 567 568 std::string sbuf; 569 llvm::raw_string_ostream os(sbuf); 570 const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S); 571 572 os << "Control jumps to line " 573 << End.asLocation().getExpansionLineNumber(); 574 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 575 os.str())); 576 break; 577 } 578 579 case Stmt::SwitchStmtClass: { 580 // Figure out what case arm we took. 581 std::string sbuf; 582 llvm::raw_string_ostream os(sbuf); 583 584 if (const Stmt *S = Dst->getLabel()) { 585 PathDiagnosticLocation End(S, SMgr); 586 587 switch (S->getStmtClass()) { 588 default: 589 os << "No cases match in the switch statement. " 590 "Control jumps to line " 591 << End.asLocation().getExpansionLineNumber(); 592 break; 593 case Stmt::DefaultStmtClass: 594 os << "Control jumps to the 'default' case at line " 595 << End.asLocation().getExpansionLineNumber(); 596 break; 597 598 case Stmt::CaseStmtClass: { 599 os << "Control jumps to 'case "; 600 const CaseStmt *Case = cast<CaseStmt>(S); 601 const Expr *LHS = Case->getLHS()->IgnoreParenCasts(); 602 603 // Determine if it is an enum. 604 bool GetRawInt = true; 605 606 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) { 607 // FIXME: Maybe this should be an assertion. Are there cases 608 // were it is not an EnumConstantDecl? 609 const EnumConstantDecl *D = 610 dyn_cast<EnumConstantDecl>(DR->getDecl()); 611 612 if (D) { 613 GetRawInt = false; 614 os << D; 615 } 616 } 617 618 if (GetRawInt) 619 os << LHS->EvaluateAsInt(PDB.getASTContext()); 620 621 os << ":' at line " 622 << End.asLocation().getExpansionLineNumber(); 623 break; 624 } 625 } 626 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 627 os.str())); 628 } 629 else { 630 os << "'Default' branch taken. "; 631 const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N); 632 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 633 os.str())); 634 } 635 636 break; 637 } 638 639 case Stmt::BreakStmtClass: 640 case Stmt::ContinueStmtClass: { 641 std::string sbuf; 642 llvm::raw_string_ostream os(sbuf); 643 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 644 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 645 os.str())); 646 break; 647 } 648 649 // Determine control-flow for ternary '?'. 650 case Stmt::BinaryConditionalOperatorClass: 651 case Stmt::ConditionalOperatorClass: { 652 std::string sbuf; 653 llvm::raw_string_ostream os(sbuf); 654 os << "'?' condition is "; 655 656 if (*(Src->succ_begin()+1) == Dst) 657 os << "false"; 658 else 659 os << "true"; 660 661 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 662 663 if (const Stmt *S = End.asStmt()) 664 End = PDB.getEnclosingStmtLocation(S); 665 666 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 667 os.str())); 668 break; 669 } 670 671 // Determine control-flow for short-circuited '&&' and '||'. 672 case Stmt::BinaryOperatorClass: { 673 if (!PDB.supportsLogicalOpControlFlow()) 674 break; 675 676 const BinaryOperator *B = cast<BinaryOperator>(T); 677 std::string sbuf; 678 llvm::raw_string_ostream os(sbuf); 679 os << "Left side of '"; 680 681 if (B->getOpcode() == BO_LAnd) { 682 os << "&&" << "' is "; 683 684 if (*(Src->succ_begin()+1) == Dst) { 685 os << "false"; 686 PathDiagnosticLocation End(B->getLHS(), SMgr); 687 PathDiagnosticLocation Start(B->getOperatorLoc(), SMgr); 688 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 689 os.str())); 690 } 691 else { 692 os << "true"; 693 PathDiagnosticLocation Start(B->getLHS(), SMgr); 694 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 695 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 696 os.str())); 697 } 698 } 699 else { 700 assert(B->getOpcode() == BO_LOr); 701 os << "||" << "' is "; 702 703 if (*(Src->succ_begin()+1) == Dst) { 704 os << "false"; 705 PathDiagnosticLocation Start(B->getLHS(), SMgr); 706 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 707 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 708 os.str())); 709 } 710 else { 711 os << "true"; 712 PathDiagnosticLocation End(B->getLHS(), SMgr); 713 PathDiagnosticLocation Start(B->getOperatorLoc(), SMgr); 714 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 715 os.str())); 716 } 717 } 718 719 break; 720 } 721 722 case Stmt::DoStmtClass: { 723 if (*(Src->succ_begin()) == Dst) { 724 std::string sbuf; 725 llvm::raw_string_ostream os(sbuf); 726 727 os << "Loop condition is true. "; 728 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 729 730 if (const Stmt *S = End.asStmt()) 731 End = PDB.getEnclosingStmtLocation(S); 732 733 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 734 os.str())); 735 } 736 else { 737 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 738 739 if (const Stmt *S = End.asStmt()) 740 End = PDB.getEnclosingStmtLocation(S); 741 742 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 743 "Loop condition is false. Exiting loop")); 744 } 745 746 break; 747 } 748 749 case Stmt::WhileStmtClass: 750 case Stmt::ForStmtClass: { 751 if (*(Src->succ_begin()+1) == Dst) { 752 std::string sbuf; 753 llvm::raw_string_ostream os(sbuf); 754 755 os << "Loop condition is false. "; 756 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 757 if (const Stmt *S = End.asStmt()) 758 End = PDB.getEnclosingStmtLocation(S); 759 760 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 761 os.str())); 762 } 763 else { 764 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 765 if (const Stmt *S = End.asStmt()) 766 End = PDB.getEnclosingStmtLocation(S); 767 768 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 769 "Loop condition is true. Entering loop body")); 770 } 771 772 break; 773 } 774 775 case Stmt::IfStmtClass: { 776 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 777 778 if (const Stmt *S = End.asStmt()) 779 End = PDB.getEnclosingStmtLocation(S); 780 781 if (*(Src->succ_begin()+1) == Dst) 782 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 783 "Taking false branch")); 784 else 785 PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 786 "Taking true branch")); 787 788 break; 789 } 790 } 791 } 792 793 if (NextNode) { 794 for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(), 795 E = PDB.visitor_end(); I!=E; ++I) { 796 if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB)) 797 PD.push_front(p); 798 } 799 } 800 801 if (const PostStmt *PS = dyn_cast<PostStmt>(&P)) { 802 // Scan the region bindings, and see if a "notable" symbol has a new 803 // lval binding. 804 ScanNotableSymbols SNS(N, PS->getStmt(), PDB.getBugReporter(), PD); 805 PDB.getStateManager().iterBindings(N->getState(), SNS); 806 } 807 } 808 809 // After constructing the full PathDiagnostic, do a pass over it to compact 810 // PathDiagnosticPieces that occur within a macro. 811 CompactPathDiagnostic(PD, PDB.getSourceManager()); 812} 813 814//===----------------------------------------------------------------------===// 815// "Extensive" PathDiagnostic generation. 816//===----------------------------------------------------------------------===// 817 818static bool IsControlFlowExpr(const Stmt *S) { 819 const Expr *E = dyn_cast<Expr>(S); 820 821 if (!E) 822 return false; 823 824 E = E->IgnoreParenCasts(); 825 826 if (isa<AbstractConditionalOperator>(E)) 827 return true; 828 829 if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E)) 830 if (B->isLogicalOp()) 831 return true; 832 833 return false; 834} 835 836namespace { 837class ContextLocation : public PathDiagnosticLocation { 838 bool IsDead; 839public: 840 ContextLocation(const PathDiagnosticLocation &L, bool isdead = false) 841 : PathDiagnosticLocation(L), IsDead(isdead) {} 842 843 void markDead() { IsDead = true; } 844 bool isDead() const { return IsDead; } 845}; 846 847class EdgeBuilder { 848 std::vector<ContextLocation> CLocs; 849 typedef std::vector<ContextLocation>::iterator iterator; 850 PathDiagnostic &PD; 851 PathDiagnosticBuilder &PDB; 852 PathDiagnosticLocation PrevLoc; 853 854 bool IsConsumedExpr(const PathDiagnosticLocation &L); 855 856 bool containsLocation(const PathDiagnosticLocation &Container, 857 const PathDiagnosticLocation &Containee); 858 859 PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L); 860 861 PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L, 862 bool firstCharOnly = false) { 863 if (const Stmt *S = L.asStmt()) { 864 const Stmt *Original = S; 865 while (1) { 866 // Adjust the location for some expressions that are best referenced 867 // by one of their subexpressions. 868 switch (S->getStmtClass()) { 869 default: 870 break; 871 case Stmt::ParenExprClass: 872 case Stmt::GenericSelectionExprClass: 873 S = cast<Expr>(S)->IgnoreParens(); 874 firstCharOnly = true; 875 continue; 876 case Stmt::BinaryConditionalOperatorClass: 877 case Stmt::ConditionalOperatorClass: 878 S = cast<AbstractConditionalOperator>(S)->getCond(); 879 firstCharOnly = true; 880 continue; 881 case Stmt::ChooseExprClass: 882 S = cast<ChooseExpr>(S)->getCond(); 883 firstCharOnly = true; 884 continue; 885 case Stmt::BinaryOperatorClass: 886 S = cast<BinaryOperator>(S)->getLHS(); 887 firstCharOnly = true; 888 continue; 889 } 890 891 break; 892 } 893 894 if (S != Original) 895 L = PathDiagnosticLocation(S, L.getManager()); 896 } 897 898 if (firstCharOnly) 899 L = PathDiagnosticLocation(L.asLocation()); 900 901 return L; 902 } 903 904 void popLocation() { 905 if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) { 906 // For contexts, we only one the first character as the range. 907 rawAddEdge(cleanUpLocation(CLocs.back(), true)); 908 } 909 CLocs.pop_back(); 910 } 911 912public: 913 EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb) 914 : PD(pd), PDB(pdb) { 915 916 // If the PathDiagnostic already has pieces, add the enclosing statement 917 // of the first piece as a context as well. 918 if (!PD.empty()) { 919 PrevLoc = PD.begin()->getLocation(); 920 921 if (const Stmt *S = PrevLoc.asStmt()) 922 addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 923 } 924 } 925 926 ~EdgeBuilder() { 927 while (!CLocs.empty()) popLocation(); 928 929 // Finally, add an initial edge from the start location of the first 930 // statement (if it doesn't already exist). 931 // FIXME: Should handle CXXTryStmt if analyser starts supporting C++. 932 if (const CompoundStmt *CS = 933 dyn_cast_or_null<CompoundStmt>(PDB.getCodeDecl().getBody())) 934 if (!CS->body_empty()) { 935 SourceLocation Loc = (*CS->body_begin())->getLocStart(); 936 rawAddEdge(PathDiagnosticLocation(Loc, PDB.getSourceManager())); 937 } 938 939 } 940 941 void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false); 942 943 void rawAddEdge(PathDiagnosticLocation NewLoc); 944 945 void addContext(const Stmt *S); 946 void addExtendedContext(const Stmt *S); 947}; 948} // end anonymous namespace 949 950 951PathDiagnosticLocation 952EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) { 953 if (const Stmt *S = L.asStmt()) { 954 if (IsControlFlowExpr(S)) 955 return L; 956 957 return PDB.getEnclosingStmtLocation(S); 958 } 959 960 return L; 961} 962 963bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container, 964 const PathDiagnosticLocation &Containee) { 965 966 if (Container == Containee) 967 return true; 968 969 if (Container.asDecl()) 970 return true; 971 972 if (const Stmt *S = Containee.asStmt()) 973 if (const Stmt *ContainerS = Container.asStmt()) { 974 while (S) { 975 if (S == ContainerS) 976 return true; 977 S = PDB.getParent(S); 978 } 979 return false; 980 } 981 982 // Less accurate: compare using source ranges. 983 SourceRange ContainerR = Container.asRange(); 984 SourceRange ContaineeR = Containee.asRange(); 985 986 SourceManager &SM = PDB.getSourceManager(); 987 SourceLocation ContainerRBeg = SM.getExpansionLoc(ContainerR.getBegin()); 988 SourceLocation ContainerREnd = SM.getExpansionLoc(ContainerR.getEnd()); 989 SourceLocation ContaineeRBeg = SM.getExpansionLoc(ContaineeR.getBegin()); 990 SourceLocation ContaineeREnd = SM.getExpansionLoc(ContaineeR.getEnd()); 991 992 unsigned ContainerBegLine = SM.getExpansionLineNumber(ContainerRBeg); 993 unsigned ContainerEndLine = SM.getExpansionLineNumber(ContainerREnd); 994 unsigned ContaineeBegLine = SM.getExpansionLineNumber(ContaineeRBeg); 995 unsigned ContaineeEndLine = SM.getExpansionLineNumber(ContaineeREnd); 996 997 assert(ContainerBegLine <= ContainerEndLine); 998 assert(ContaineeBegLine <= ContaineeEndLine); 999 1000 return (ContainerBegLine <= ContaineeBegLine && 1001 ContainerEndLine >= ContaineeEndLine && 1002 (ContainerBegLine != ContaineeBegLine || 1003 SM.getExpansionColumnNumber(ContainerRBeg) <= 1004 SM.getExpansionColumnNumber(ContaineeRBeg)) && 1005 (ContainerEndLine != ContaineeEndLine || 1006 SM.getExpansionColumnNumber(ContainerREnd) >= 1007 SM.getExpansionColumnNumber(ContainerREnd))); 1008} 1009 1010void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) { 1011 if (!PrevLoc.isValid()) { 1012 PrevLoc = NewLoc; 1013 return; 1014 } 1015 1016 const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc); 1017 const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc); 1018 1019 if (NewLocClean.asLocation() == PrevLocClean.asLocation()) 1020 return; 1021 1022 // FIXME: Ignore intra-macro edges for now. 1023 if (NewLocClean.asLocation().getExpansionLoc() == 1024 PrevLocClean.asLocation().getExpansionLoc()) 1025 return; 1026 1027 PD.push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean)); 1028 PrevLoc = NewLoc; 1029} 1030 1031void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd) { 1032 1033 if (!alwaysAdd && NewLoc.asLocation().isMacroID()) 1034 return; 1035 1036 const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc); 1037 1038 while (!CLocs.empty()) { 1039 ContextLocation &TopContextLoc = CLocs.back(); 1040 1041 // Is the top location context the same as the one for the new location? 1042 if (TopContextLoc == CLoc) { 1043 if (alwaysAdd) { 1044 if (IsConsumedExpr(TopContextLoc) && 1045 !IsControlFlowExpr(TopContextLoc.asStmt())) 1046 TopContextLoc.markDead(); 1047 1048 rawAddEdge(NewLoc); 1049 } 1050 1051 return; 1052 } 1053 1054 if (containsLocation(TopContextLoc, CLoc)) { 1055 if (alwaysAdd) { 1056 rawAddEdge(NewLoc); 1057 1058 if (IsConsumedExpr(CLoc) && !IsControlFlowExpr(CLoc.asStmt())) { 1059 CLocs.push_back(ContextLocation(CLoc, true)); 1060 return; 1061 } 1062 } 1063 1064 CLocs.push_back(CLoc); 1065 return; 1066 } 1067 1068 // Context does not contain the location. Flush it. 1069 popLocation(); 1070 } 1071 1072 // If we reach here, there is no enclosing context. Just add the edge. 1073 rawAddEdge(NewLoc); 1074} 1075 1076bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) { 1077 if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt())) 1078 return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X); 1079 1080 return false; 1081} 1082 1083void EdgeBuilder::addExtendedContext(const Stmt *S) { 1084 if (!S) 1085 return; 1086 1087 const Stmt *Parent = PDB.getParent(S); 1088 while (Parent) { 1089 if (isa<CompoundStmt>(Parent)) 1090 Parent = PDB.getParent(Parent); 1091 else 1092 break; 1093 } 1094 1095 if (Parent) { 1096 switch (Parent->getStmtClass()) { 1097 case Stmt::DoStmtClass: 1098 case Stmt::ObjCAtSynchronizedStmtClass: 1099 addContext(Parent); 1100 default: 1101 break; 1102 } 1103 } 1104 1105 addContext(S); 1106} 1107 1108void EdgeBuilder::addContext(const Stmt *S) { 1109 if (!S) 1110 return; 1111 1112 PathDiagnosticLocation L(S, PDB.getSourceManager()); 1113 1114 while (!CLocs.empty()) { 1115 const PathDiagnosticLocation &TopContextLoc = CLocs.back(); 1116 1117 // Is the top location context the same as the one for the new location? 1118 if (TopContextLoc == L) 1119 return; 1120 1121 if (containsLocation(TopContextLoc, L)) { 1122 CLocs.push_back(L); 1123 return; 1124 } 1125 1126 // Context does not contain the location. Flush it. 1127 popLocation(); 1128 } 1129 1130 CLocs.push_back(L); 1131} 1132 1133static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD, 1134 PathDiagnosticBuilder &PDB, 1135 const ExplodedNode *N) { 1136 EdgeBuilder EB(PD, PDB); 1137 1138 const ExplodedNode *NextNode = N->pred_empty() ? NULL : *(N->pred_begin()); 1139 while (NextNode) { 1140 N = NextNode; 1141 NextNode = GetPredecessorNode(N); 1142 ProgramPoint P = N->getLocation(); 1143 1144 do { 1145 // Block edges. 1146 if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { 1147 const CFGBlock &Blk = *BE->getSrc(); 1148 const Stmt *Term = Blk.getTerminator(); 1149 1150 // Are we jumping to the head of a loop? Add a special diagnostic. 1151 if (const Stmt *Loop = BE->getDst()->getLoopTarget()) { 1152 PathDiagnosticLocation L(Loop, PDB.getSourceManager()); 1153 const CompoundStmt *CS = NULL; 1154 1155 if (!Term) { 1156 if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) 1157 CS = dyn_cast<CompoundStmt>(FS->getBody()); 1158 else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) 1159 CS = dyn_cast<CompoundStmt>(WS->getBody()); 1160 } 1161 1162 PathDiagnosticEventPiece *p = 1163 new PathDiagnosticEventPiece(L, 1164 "Looping back to the head of the loop"); 1165 1166 EB.addEdge(p->getLocation(), true); 1167 PD.push_front(p); 1168 1169 if (CS) { 1170 PathDiagnosticLocation BL(CS->getRBracLoc(), 1171 PDB.getSourceManager()); 1172 BL = PathDiagnosticLocation(BL.asLocation()); 1173 EB.addEdge(BL); 1174 } 1175 } 1176 1177 if (Term) 1178 EB.addContext(Term); 1179 1180 break; 1181 } 1182 1183 if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) { 1184 if (const CFGStmt *S = BE->getFirstElement().getAs<CFGStmt>()) { 1185 const Stmt *stmt = S->getStmt(); 1186 if (IsControlFlowExpr(stmt)) { 1187 // Add the proper context for '&&', '||', and '?'. 1188 EB.addContext(stmt); 1189 } 1190 else 1191 EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt()); 1192 } 1193 1194 break; 1195 } 1196 } while (0); 1197 1198 if (!NextNode) 1199 continue; 1200 1201 for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(), 1202 E = PDB.visitor_end(); I!=E; ++I) { 1203 if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB)) { 1204 const PathDiagnosticLocation &Loc = p->getLocation(); 1205 EB.addEdge(Loc, true); 1206 PD.push_front(p); 1207 if (const Stmt *S = Loc.asStmt()) 1208 EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 1209 } 1210 } 1211 } 1212} 1213 1214//===----------------------------------------------------------------------===// 1215// Methods for BugType and subclasses. 1216//===----------------------------------------------------------------------===// 1217BugType::~BugType() { } 1218 1219void BugType::FlushReports(BugReporter &BR) {} 1220 1221//===----------------------------------------------------------------------===// 1222// Methods for BugReport and subclasses. 1223//===----------------------------------------------------------------------===// 1224 1225BugReport::~BugReport() {} 1226 1227void BugReport::Profile(llvm::FoldingSetNodeID& hash) const { 1228 hash.AddPointer(&BT); 1229 hash.AddInteger(getLocation().getRawEncoding()); 1230 hash.AddString(Description); 1231 1232 for (SmallVectorImpl<SourceRange>::const_iterator I = 1233 Ranges.begin(), E = Ranges.end(); I != E; ++I) { 1234 const SourceRange range = *I; 1235 if (!range.isValid()) 1236 continue; 1237 hash.AddInteger(range.getBegin().getRawEncoding()); 1238 hash.AddInteger(range.getEnd().getRawEncoding()); 1239 } 1240} 1241 1242const Stmt *BugReport::getStmt() const { 1243 if (!ErrorNode) 1244 return 0; 1245 1246 ProgramPoint ProgP = ErrorNode->getLocation(); 1247 const Stmt *S = NULL; 1248 1249 if (BlockEntrance *BE = dyn_cast<BlockEntrance>(&ProgP)) { 1250 CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit(); 1251 if (BE->getBlock() == &Exit) 1252 S = GetPreviousStmt(ErrorNode); 1253 } 1254 if (!S) 1255 S = GetStmt(ProgP); 1256 1257 return S; 1258} 1259 1260PathDiagnosticPiece* 1261BugReport::getEndPath(BugReporterContext &BRC, 1262 const ExplodedNode *EndPathNode) { 1263 1264 const ProgramPoint &PP = EndPathNode->getLocation(); 1265 PathDiagnosticLocation L; 1266 1267 if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&PP)) { 1268 const CFGBlock *block = BE->getBlock(); 1269 if (block->getBlockID() == 0) { 1270 L = PathDiagnosticLocation( 1271 EndPathNode->getLocationContext()->getDecl()->getBodyRBrace(), 1272 BRC.getSourceManager()); 1273 } 1274 } 1275 1276 if (!L.isValid()) { 1277 const Stmt *S = getStmt(); 1278 1279 if (!S) 1280 return NULL; 1281 1282 L = PathDiagnosticLocation(S, BRC.getSourceManager()); 1283 } 1284 1285 BugReport::ranges_iterator Beg, End; 1286 llvm::tie(Beg, End) = getRanges(); 1287 1288 // Only add the statement itself as a range if we didn't specify any 1289 // special ranges for this report. 1290 PathDiagnosticPiece *P = new PathDiagnosticEventPiece(L, getDescription(), 1291 Beg == End); 1292 1293 for (; Beg != End; ++Beg) 1294 P->addRange(*Beg); 1295 1296 return P; 1297} 1298 1299std::pair<BugReport::ranges_iterator, BugReport::ranges_iterator> 1300BugReport::getRanges() { 1301 // If no custom ranges, add the range of the statement corresponding to 1302 // the error node. 1303 if (Ranges.empty()) { 1304 if (const Expr *E = dyn_cast_or_null<Expr>(getStmt())) 1305 addRange(E->getSourceRange()); 1306 else 1307 return std::make_pair(ranges_iterator(), ranges_iterator()); 1308 } 1309 1310 return std::make_pair(Ranges.begin(), Ranges.end()); 1311} 1312 1313SourceLocation BugReport::getLocation() const { 1314 if (ErrorNode) 1315 if (const Stmt *S = GetCurrentOrPreviousStmt(ErrorNode)) { 1316 // For member expressions, return the location of the '.' or '->'. 1317 if (const MemberExpr *ME = dyn_cast<MemberExpr>(S)) 1318 return ME->getMemberLoc(); 1319 // For binary operators, return the location of the operator. 1320 if (const BinaryOperator *B = dyn_cast<BinaryOperator>(S)) 1321 return B->getOperatorLoc(); 1322 1323 return S->getLocStart(); 1324 } 1325 1326 return FullSourceLoc(); 1327} 1328 1329PathDiagnosticPiece *BugReport::VisitNode(const ExplodedNode *N, 1330 const ExplodedNode *PrevN, 1331 BugReporterContext &BRC) { 1332 return NULL; 1333} 1334 1335//===----------------------------------------------------------------------===// 1336// Methods for BugReporter and subclasses. 1337//===----------------------------------------------------------------------===// 1338 1339BugReportEquivClass::~BugReportEquivClass() { 1340 for (iterator I=begin(), E=end(); I!=E; ++I) delete *I; 1341} 1342 1343GRBugReporter::~GRBugReporter() { } 1344BugReporterData::~BugReporterData() {} 1345 1346ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); } 1347 1348ProgramStateManager& 1349GRBugReporter::getStateManager() { return Eng.getStateManager(); } 1350 1351BugReporter::~BugReporter() { FlushReports(); } 1352 1353void BugReporter::FlushReports() { 1354 if (BugTypes.isEmpty()) 1355 return; 1356 1357 // First flush the warnings for each BugType. This may end up creating new 1358 // warnings and new BugTypes. 1359 // FIXME: Only NSErrorChecker needs BugType's FlushReports. 1360 // Turn NSErrorChecker into a proper checker and remove this. 1361 SmallVector<const BugType*, 16> bugTypes; 1362 for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I) 1363 bugTypes.push_back(*I); 1364 for (SmallVector<const BugType*, 16>::iterator 1365 I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I) 1366 const_cast<BugType*>(*I)->FlushReports(*this); 1367 1368 typedef llvm::FoldingSet<BugReportEquivClass> SetTy; 1369 for (SetTy::iterator EI=EQClasses.begin(), EE=EQClasses.end(); EI!=EE;++EI){ 1370 BugReportEquivClass& EQ = *EI; 1371 FlushReport(EQ); 1372 } 1373 1374 // BugReporter owns and deletes only BugTypes created implicitly through 1375 // EmitBasicReport. 1376 // FIXME: There are leaks from checkers that assume that the BugTypes they 1377 // create will be destroyed by the BugReporter. 1378 for (llvm::StringMap<BugType*>::iterator 1379 I = StrBugTypes.begin(), E = StrBugTypes.end(); I != E; ++I) 1380 delete I->second; 1381 1382 // Remove all references to the BugType objects. 1383 BugTypes = F.getEmptySet(); 1384} 1385 1386//===----------------------------------------------------------------------===// 1387// PathDiagnostics generation. 1388//===----------------------------------------------------------------------===// 1389 1390static std::pair<std::pair<ExplodedGraph*, NodeBackMap*>, 1391 std::pair<ExplodedNode*, unsigned> > 1392MakeReportGraph(const ExplodedGraph* G, 1393 SmallVectorImpl<const ExplodedNode*> &nodes) { 1394 1395 // Create the trimmed graph. It will contain the shortest paths from the 1396 // error nodes to the root. In the new graph we should only have one 1397 // error node unless there are two or more error nodes with the same minimum 1398 // path length. 1399 ExplodedGraph* GTrim; 1400 InterExplodedGraphMap* NMap; 1401 1402 llvm::DenseMap<const void*, const void*> InverseMap; 1403 llvm::tie(GTrim, NMap) = G->Trim(nodes.data(), nodes.data() + nodes.size(), 1404 &InverseMap); 1405 1406 // Create owning pointers for GTrim and NMap just to ensure that they are 1407 // released when this function exists. 1408 llvm::OwningPtr<ExplodedGraph> AutoReleaseGTrim(GTrim); 1409 llvm::OwningPtr<InterExplodedGraphMap> AutoReleaseNMap(NMap); 1410 1411 // Find the (first) error node in the trimmed graph. We just need to consult 1412 // the node map (NMap) which maps from nodes in the original graph to nodes 1413 // in the new graph. 1414 1415 std::queue<const ExplodedNode*> WS; 1416 typedef llvm::DenseMap<const ExplodedNode*, unsigned> IndexMapTy; 1417 IndexMapTy IndexMap; 1418 1419 for (unsigned nodeIndex = 0 ; nodeIndex < nodes.size(); ++nodeIndex) { 1420 const ExplodedNode *originalNode = nodes[nodeIndex]; 1421 if (const ExplodedNode *N = NMap->getMappedNode(originalNode)) { 1422 WS.push(N); 1423 IndexMap[originalNode] = nodeIndex; 1424 } 1425 } 1426 1427 assert(!WS.empty() && "No error node found in the trimmed graph."); 1428 1429 // Create a new (third!) graph with a single path. This is the graph 1430 // that will be returned to the caller. 1431 ExplodedGraph *GNew = new ExplodedGraph(); 1432 1433 // Sometimes the trimmed graph can contain a cycle. Perform a reverse BFS 1434 // to the root node, and then construct a new graph that contains only 1435 // a single path. 1436 llvm::DenseMap<const void*,unsigned> Visited; 1437 1438 unsigned cnt = 0; 1439 const ExplodedNode *Root = 0; 1440 1441 while (!WS.empty()) { 1442 const ExplodedNode *Node = WS.front(); 1443 WS.pop(); 1444 1445 if (Visited.find(Node) != Visited.end()) 1446 continue; 1447 1448 Visited[Node] = cnt++; 1449 1450 if (Node->pred_empty()) { 1451 Root = Node; 1452 break; 1453 } 1454 1455 for (ExplodedNode::const_pred_iterator I=Node->pred_begin(), 1456 E=Node->pred_end(); I!=E; ++I) 1457 WS.push(*I); 1458 } 1459 1460 assert(Root); 1461 1462 // Now walk from the root down the BFS path, always taking the successor 1463 // with the lowest number. 1464 ExplodedNode *Last = 0, *First = 0; 1465 NodeBackMap *BM = new NodeBackMap(); 1466 unsigned NodeIndex = 0; 1467 1468 for ( const ExplodedNode *N = Root ;;) { 1469 // Lookup the number associated with the current node. 1470 llvm::DenseMap<const void*,unsigned>::iterator I = Visited.find(N); 1471 assert(I != Visited.end()); 1472 1473 // Create the equivalent node in the new graph with the same state 1474 // and location. 1475 ExplodedNode *NewN = GNew->getNode(N->getLocation(), N->getState()); 1476 1477 // Store the mapping to the original node. 1478 llvm::DenseMap<const void*, const void*>::iterator IMitr=InverseMap.find(N); 1479 assert(IMitr != InverseMap.end() && "No mapping to original node."); 1480 (*BM)[NewN] = (const ExplodedNode*) IMitr->second; 1481 1482 // Link up the new node with the previous node. 1483 if (Last) 1484 NewN->addPredecessor(Last, *GNew); 1485 1486 Last = NewN; 1487 1488 // Are we at the final node? 1489 IndexMapTy::iterator IMI = 1490 IndexMap.find((const ExplodedNode*)(IMitr->second)); 1491 if (IMI != IndexMap.end()) { 1492 First = NewN; 1493 NodeIndex = IMI->second; 1494 break; 1495 } 1496 1497 // Find the next successor node. We choose the node that is marked 1498 // with the lowest DFS number. 1499 ExplodedNode::const_succ_iterator SI = N->succ_begin(); 1500 ExplodedNode::const_succ_iterator SE = N->succ_end(); 1501 N = 0; 1502 1503 for (unsigned MinVal = 0; SI != SE; ++SI) { 1504 1505 I = Visited.find(*SI); 1506 1507 if (I == Visited.end()) 1508 continue; 1509 1510 if (!N || I->second < MinVal) { 1511 N = *SI; 1512 MinVal = I->second; 1513 } 1514 } 1515 1516 assert(N); 1517 } 1518 1519 assert(First); 1520 1521 return std::make_pair(std::make_pair(GNew, BM), 1522 std::make_pair(First, NodeIndex)); 1523} 1524 1525/// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object 1526/// and collapses PathDiagosticPieces that are expanded by macros. 1527static void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM) { 1528 typedef std::vector<std::pair<PathDiagnosticMacroPiece*, SourceLocation> > 1529 MacroStackTy; 1530 1531 typedef std::vector<PathDiagnosticPiece*> 1532 PiecesTy; 1533 1534 MacroStackTy MacroStack; 1535 PiecesTy Pieces; 1536 1537 for (PathDiagnostic::iterator I = PD.begin(), E = PD.end(); I!=E; ++I) { 1538 // Get the location of the PathDiagnosticPiece. 1539 const FullSourceLoc Loc = I->getLocation().asLocation(); 1540 1541 // Determine the instantiation location, which is the location we group 1542 // related PathDiagnosticPieces. 1543 SourceLocation InstantiationLoc = Loc.isMacroID() ? 1544 SM.getExpansionLoc(Loc) : 1545 SourceLocation(); 1546 1547 if (Loc.isFileID()) { 1548 MacroStack.clear(); 1549 Pieces.push_back(&*I); 1550 continue; 1551 } 1552 1553 assert(Loc.isMacroID()); 1554 1555 // Is the PathDiagnosticPiece within the same macro group? 1556 if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) { 1557 MacroStack.back().first->push_back(&*I); 1558 continue; 1559 } 1560 1561 // We aren't in the same group. Are we descending into a new macro 1562 // or are part of an old one? 1563 PathDiagnosticMacroPiece *MacroGroup = 0; 1564 1565 SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ? 1566 SM.getExpansionLoc(Loc) : 1567 SourceLocation(); 1568 1569 // Walk the entire macro stack. 1570 while (!MacroStack.empty()) { 1571 if (InstantiationLoc == MacroStack.back().second) { 1572 MacroGroup = MacroStack.back().first; 1573 break; 1574 } 1575 1576 if (ParentInstantiationLoc == MacroStack.back().second) { 1577 MacroGroup = MacroStack.back().first; 1578 break; 1579 } 1580 1581 MacroStack.pop_back(); 1582 } 1583 1584 if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) { 1585 // Create a new macro group and add it to the stack. 1586 PathDiagnosticMacroPiece *NewGroup = new PathDiagnosticMacroPiece(Loc); 1587 1588 if (MacroGroup) 1589 MacroGroup->push_back(NewGroup); 1590 else { 1591 assert(InstantiationLoc.isFileID()); 1592 Pieces.push_back(NewGroup); 1593 } 1594 1595 MacroGroup = NewGroup; 1596 MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc)); 1597 } 1598 1599 // Finally, add the PathDiagnosticPiece to the group. 1600 MacroGroup->push_back(&*I); 1601 } 1602 1603 // Now take the pieces and construct a new PathDiagnostic. 1604 PD.resetPath(false); 1605 1606 for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I) { 1607 if (PathDiagnosticMacroPiece *MP=dyn_cast<PathDiagnosticMacroPiece>(*I)) 1608 if (!MP->containsEvent()) { 1609 delete MP; 1610 continue; 1611 } 1612 1613 PD.push_back(*I); 1614 } 1615} 1616 1617void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, 1618 SmallVectorImpl<BugReport *> &bugReports) { 1619 1620 assert(!bugReports.empty()); 1621 SmallVector<const ExplodedNode *, 10> errorNodes; 1622 for (SmallVectorImpl<BugReport*>::iterator I = bugReports.begin(), 1623 E = bugReports.end(); I != E; ++I) { 1624 errorNodes.push_back((*I)->getErrorNode()); 1625 } 1626 1627 // Construct a new graph that contains only a single path from the error 1628 // node to a root. 1629 const std::pair<std::pair<ExplodedGraph*, NodeBackMap*>, 1630 std::pair<ExplodedNode*, unsigned> >& 1631 GPair = MakeReportGraph(&getGraph(), errorNodes); 1632 1633 // Find the BugReport with the original location. 1634 assert(GPair.second.second < bugReports.size()); 1635 BugReport *R = bugReports[GPair.second.second]; 1636 assert(R && "No original report found for sliced graph."); 1637 1638 llvm::OwningPtr<ExplodedGraph> ReportGraph(GPair.first.first); 1639 llvm::OwningPtr<NodeBackMap> BackMap(GPair.first.second); 1640 const ExplodedNode *N = GPair.second.first; 1641 1642 // Start building the path diagnostic... 1643 PathDiagnosticBuilder PDB(*this, R, BackMap.get(), getPathDiagnosticClient()); 1644 1645 if (PathDiagnosticPiece *Piece = R->getEndPath(PDB, N)) 1646 PD.push_back(Piece); 1647 else 1648 return; 1649 1650 // Register node visitors. 1651 R->registerInitialVisitors(PDB, N); 1652 bugreporter::registerNilReceiverVisitor(PDB); 1653 bugreporter::registerConditionVisitor(PDB); 1654 1655 switch (PDB.getGenerationScheme()) { 1656 case PathDiagnosticClient::Extensive: 1657 GenerateExtensivePathDiagnostic(PD, PDB, N); 1658 break; 1659 case PathDiagnosticClient::Minimal: 1660 GenerateMinimalPathDiagnostic(PD, PDB, N); 1661 break; 1662 } 1663} 1664 1665void BugReporter::Register(BugType *BT) { 1666 BugTypes = F.add(BugTypes, BT); 1667} 1668 1669void BugReporter::EmitReport(BugReport* R) { 1670 // Compute the bug report's hash to determine its equivalence class. 1671 llvm::FoldingSetNodeID ID; 1672 R->Profile(ID); 1673 1674 // Lookup the equivance class. If there isn't one, create it. 1675 BugType& BT = R->getBugType(); 1676 Register(&BT); 1677 void *InsertPos; 1678 BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos); 1679 1680 if (!EQ) { 1681 EQ = new BugReportEquivClass(R); 1682 EQClasses.InsertNode(EQ, InsertPos); 1683 } 1684 else 1685 EQ->AddReport(R); 1686} 1687 1688 1689//===----------------------------------------------------------------------===// 1690// Emitting reports in equivalence classes. 1691//===----------------------------------------------------------------------===// 1692 1693namespace { 1694struct FRIEC_WLItem { 1695 const ExplodedNode *N; 1696 ExplodedNode::const_succ_iterator I, E; 1697 1698 FRIEC_WLItem(const ExplodedNode *n) 1699 : N(n), I(N->succ_begin()), E(N->succ_end()) {} 1700}; 1701} 1702 1703static BugReport * 1704FindReportInEquivalenceClass(BugReportEquivClass& EQ, 1705 SmallVectorImpl<BugReport*> &bugReports) { 1706 1707 BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end(); 1708 assert(I != E); 1709 BugReport *R = *I; 1710 BugType& BT = R->getBugType(); 1711 1712 // If we don't need to suppress any of the nodes because they are 1713 // post-dominated by a sink, simply add all the nodes in the equivalence class 1714 // to 'Nodes'. Any of the reports will serve as a "representative" report. 1715 if (!BT.isSuppressOnSink()) { 1716 for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) { 1717 const ExplodedNode *N = I->getErrorNode(); 1718 if (N) { 1719 R = *I; 1720 bugReports.push_back(R); 1721 } 1722 } 1723 return R; 1724 } 1725 1726 // For bug reports that should be suppressed when all paths are post-dominated 1727 // by a sink node, iterate through the reports in the equivalence class 1728 // until we find one that isn't post-dominated (if one exists). We use a 1729 // DFS traversal of the ExplodedGraph to find a non-sink node. We could write 1730 // this as a recursive function, but we don't want to risk blowing out the 1731 // stack for very long paths. 1732 BugReport *exampleReport = 0; 1733 1734 for (; I != E; ++I) { 1735 R = *I; 1736 const ExplodedNode *errorNode = R->getErrorNode(); 1737 1738 if (!errorNode) 1739 continue; 1740 if (errorNode->isSink()) { 1741 assert(false && 1742 "BugType::isSuppressSink() should not be 'true' for sink end nodes"); 1743 return 0; 1744 } 1745 // No successors? By definition this nodes isn't post-dominated by a sink. 1746 if (errorNode->succ_empty()) { 1747 bugReports.push_back(R); 1748 if (!exampleReport) 1749 exampleReport = R; 1750 continue; 1751 } 1752 1753 // At this point we know that 'N' is not a sink and it has at least one 1754 // successor. Use a DFS worklist to find a non-sink end-of-path node. 1755 typedef FRIEC_WLItem WLItem; 1756 typedef SmallVector<WLItem, 10> DFSWorkList; 1757 llvm::DenseMap<const ExplodedNode *, unsigned> Visited; 1758 1759 DFSWorkList WL; 1760 WL.push_back(errorNode); 1761 Visited[errorNode] = 1; 1762 1763 while (!WL.empty()) { 1764 WLItem &WI = WL.back(); 1765 assert(!WI.N->succ_empty()); 1766 1767 for (; WI.I != WI.E; ++WI.I) { 1768 const ExplodedNode *Succ = *WI.I; 1769 // End-of-path node? 1770 if (Succ->succ_empty()) { 1771 // If we found an end-of-path node that is not a sink. 1772 if (!Succ->isSink()) { 1773 bugReports.push_back(R); 1774 if (!exampleReport) 1775 exampleReport = R; 1776 WL.clear(); 1777 break; 1778 } 1779 // Found a sink? Continue on to the next successor. 1780 continue; 1781 } 1782 // Mark the successor as visited. If it hasn't been explored, 1783 // enqueue it to the DFS worklist. 1784 unsigned &mark = Visited[Succ]; 1785 if (!mark) { 1786 mark = 1; 1787 WL.push_back(Succ); 1788 break; 1789 } 1790 } 1791 1792 // The worklist may have been cleared at this point. First 1793 // check if it is empty before checking the last item. 1794 if (!WL.empty() && &WL.back() == &WI) 1795 WL.pop_back(); 1796 } 1797 } 1798 1799 // ExampleReport will be NULL if all the nodes in the equivalence class 1800 // were post-dominated by sinks. 1801 return exampleReport; 1802} 1803 1804//===----------------------------------------------------------------------===// 1805// DiagnosticCache. This is a hack to cache analyzer diagnostics. It 1806// uses global state, which eventually should go elsewhere. 1807//===----------------------------------------------------------------------===// 1808namespace { 1809class DiagCacheItem : public llvm::FoldingSetNode { 1810 llvm::FoldingSetNodeID ID; 1811public: 1812 DiagCacheItem(BugReport *R, PathDiagnostic *PD) { 1813 ID.AddString(R->getBugType().getName()); 1814 ID.AddString(R->getBugType().getCategory()); 1815 ID.AddString(R->getDescription()); 1816 ID.AddInteger(R->getLocation().getRawEncoding()); 1817 PD->Profile(ID); 1818 } 1819 1820 void Profile(llvm::FoldingSetNodeID &id) { 1821 id = ID; 1822 } 1823 1824 llvm::FoldingSetNodeID &getID() { return ID; } 1825}; 1826} 1827 1828static bool IsCachedDiagnostic(BugReport *R, PathDiagnostic *PD) { 1829 // FIXME: Eventually this diagnostic cache should reside in something 1830 // like AnalysisManager instead of being a static variable. This is 1831 // really unsafe in the long term. 1832 typedef llvm::FoldingSet<DiagCacheItem> DiagnosticCache; 1833 static DiagnosticCache DC; 1834 1835 void *InsertPos; 1836 DiagCacheItem *Item = new DiagCacheItem(R, PD); 1837 1838 if (DC.FindNodeOrInsertPos(Item->getID(), InsertPos)) { 1839 delete Item; 1840 return true; 1841 } 1842 1843 DC.InsertNode(Item, InsertPos); 1844 return false; 1845} 1846 1847void BugReporter::FlushReport(BugReportEquivClass& EQ) { 1848 SmallVector<BugReport*, 10> bugReports; 1849 BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports); 1850 if (!exampleReport) 1851 return; 1852 1853 PathDiagnosticClient* PD = getPathDiagnosticClient(); 1854 1855 // FIXME: Make sure we use the 'R' for the path that was actually used. 1856 // Probably doesn't make a difference in practice. 1857 BugType& BT = exampleReport->getBugType(); 1858 1859 llvm::OwningPtr<PathDiagnostic> 1860 D(new PathDiagnostic(exampleReport->getBugType().getName(), 1861 !PD || PD->useVerboseDescription() 1862 ? exampleReport->getDescription() 1863 : exampleReport->getShortDescription(), 1864 BT.getCategory())); 1865 1866 if (!bugReports.empty()) 1867 GeneratePathDiagnostic(*D.get(), bugReports); 1868 1869 if (IsCachedDiagnostic(exampleReport, D.get())) 1870 return; 1871 1872 // Get the meta data. 1873 std::pair<const char**, const char**> Meta = 1874 exampleReport->getExtraDescriptiveText(); 1875 for (const char** s = Meta.first; s != Meta.second; ++s) 1876 D->addMeta(*s); 1877 1878 // Emit a summary diagnostic to the regular Diagnostics engine. 1879 BugReport::ranges_iterator Beg, End; 1880 llvm::tie(Beg, End) = exampleReport->getRanges(); 1881 Diagnostic &Diag = getDiagnostic(); 1882 FullSourceLoc L(exampleReport->getLocation(), getSourceManager()); 1883 1884 // Search the description for '%', as that will be interpretted as a 1885 // format character by FormatDiagnostics. 1886 StringRef desc = exampleReport->getShortDescription(); 1887 unsigned ErrorDiag; 1888 { 1889 llvm::SmallString<512> TmpStr; 1890 llvm::raw_svector_ostream Out(TmpStr); 1891 for (StringRef::iterator I=desc.begin(), E=desc.end(); I!=E; ++I) 1892 if (*I == '%') 1893 Out << "%%"; 1894 else 1895 Out << *I; 1896 1897 Out.flush(); 1898 ErrorDiag = Diag.getCustomDiagID(Diagnostic::Warning, TmpStr); 1899 } 1900 1901 { 1902 DiagnosticBuilder diagBuilder = Diag.Report(L, ErrorDiag); 1903 for (BugReport::ranges_iterator I = Beg; I != End; ++I) 1904 diagBuilder << *I; 1905 } 1906 1907 // Emit a full diagnostic for the path if we have a PathDiagnosticClient. 1908 if (!PD) 1909 return; 1910 1911 if (D->empty()) { 1912 PathDiagnosticPiece *piece = 1913 new PathDiagnosticEventPiece(L, exampleReport->getDescription()); 1914 1915 for ( ; Beg != End; ++Beg) piece->addRange(*Beg); 1916 D->push_back(piece); 1917 } 1918 1919 PD->HandlePathDiagnostic(D.take()); 1920} 1921 1922void BugReporter::EmitBasicReport(StringRef name, StringRef str, 1923 SourceLocation Loc, 1924 SourceRange* RBeg, unsigned NumRanges) { 1925 EmitBasicReport(name, "", str, Loc, RBeg, NumRanges); 1926} 1927 1928void BugReporter::EmitBasicReport(StringRef name, 1929 StringRef category, 1930 StringRef str, SourceLocation Loc, 1931 SourceRange* RBeg, unsigned NumRanges) { 1932 1933 // 'BT' is owned by BugReporter. 1934 BugType *BT = getBugTypeForName(name, category); 1935 FullSourceLoc L = getContext().getFullLoc(Loc); 1936 BugReport *R = new DiagBugReport(*BT, str, L); 1937 for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg); 1938 EmitReport(R); 1939} 1940 1941BugType *BugReporter::getBugTypeForName(StringRef name, 1942 StringRef category) { 1943 llvm::SmallString<136> fullDesc; 1944 llvm::raw_svector_ostream(fullDesc) << name << ":" << category; 1945 llvm::StringMapEntry<BugType *> & 1946 entry = StrBugTypes.GetOrCreateValue(fullDesc); 1947 BugType *BT = entry.getValue(); 1948 if (!BT) { 1949 BT = new BugType(name, category); 1950 entry.setValue(BT); 1951 } 1952 return BT; 1953} 1954