BugReporter.cpp revision 219077
1218887Sdim// BugReporter.cpp - Generate PathDiagnostics for Bugs ------------*- C++ -*--// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines BugReporter, a utility class for generating 11218887Sdim// PathDiagnostics. 12218887Sdim// 13218887Sdim//===----------------------------------------------------------------------===// 14218887Sdim 15218887Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 16218887Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 17218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 18218887Sdim#include "clang/AST/ASTContext.h" 19218887Sdim#include "clang/Analysis/CFG.h" 20218887Sdim#include "clang/AST/Expr.h" 21218887Sdim#include "clang/AST/ParentMap.h" 22218887Sdim#include "clang/AST/StmtObjC.h" 23218887Sdim#include "clang/Basic/SourceManager.h" 24218887Sdim#include "clang/Analysis/ProgramPoint.h" 25218887Sdim#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" 26218887Sdim#include "llvm/Support/raw_ostream.h" 27218887Sdim#include "llvm/ADT/DenseMap.h" 28218887Sdim#include "llvm/ADT/STLExtras.h" 29218887Sdim#include "llvm/ADT/OwningPtr.h" 30218887Sdim#include <queue> 31218887Sdim 32218887Sdimusing namespace clang; 33218887Sdimusing namespace ento; 34218887Sdim 35218887SdimBugReporterVisitor::~BugReporterVisitor() {} 36218887SdimBugReporterContext::~BugReporterContext() { 37218887Sdim for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I) 38218887Sdim if ((*I)->isOwnedByReporterContext()) delete *I; 39218887Sdim} 40218887Sdim 41218887Sdimvoid BugReporterContext::addVisitor(BugReporterVisitor* visitor) { 42218887Sdim if (!visitor) 43218887Sdim return; 44218887Sdim 45218887Sdim llvm::FoldingSetNodeID ID; 46218887Sdim visitor->Profile(ID); 47218887Sdim void *InsertPos; 48218887Sdim 49218887Sdim if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) { 50218887Sdim delete visitor; 51218887Sdim return; 52218887Sdim } 53218887Sdim 54218887Sdim CallbacksSet.InsertNode(visitor, InsertPos); 55218887Sdim Callbacks = F.add(visitor, Callbacks); 56218887Sdim} 57218887Sdim 58218887Sdim//===----------------------------------------------------------------------===// 59218887Sdim// Helper routines for walking the ExplodedGraph and fetching statements. 60218887Sdim//===----------------------------------------------------------------------===// 61218887Sdim 62218887Sdimstatic inline const Stmt* GetStmt(const ProgramPoint &P) { 63218887Sdim if (const StmtPoint* SP = dyn_cast<StmtPoint>(&P)) 64218887Sdim return SP->getStmt(); 65218887Sdim else if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P)) 66218887Sdim return BE->getSrc()->getTerminator(); 67218887Sdim 68218887Sdim return 0; 69218887Sdim} 70218887Sdim 71218887Sdimstatic inline const ExplodedNode* 72218887SdimGetPredecessorNode(const ExplodedNode* N) { 73218887Sdim return N->pred_empty() ? NULL : *(N->pred_begin()); 74218887Sdim} 75218887Sdim 76218887Sdimstatic inline const ExplodedNode* 77218887SdimGetSuccessorNode(const ExplodedNode* N) { 78218887Sdim return N->succ_empty() ? NULL : *(N->succ_begin()); 79218887Sdim} 80218887Sdim 81218887Sdimstatic const Stmt* GetPreviousStmt(const ExplodedNode* N) { 82218887Sdim for (N = GetPredecessorNode(N); N; N = GetPredecessorNode(N)) 83218887Sdim if (const Stmt *S = GetStmt(N->getLocation())) 84218887Sdim return S; 85218887Sdim 86218887Sdim return 0; 87218887Sdim} 88218887Sdim 89218887Sdimstatic const Stmt* GetNextStmt(const ExplodedNode* N) { 90218887Sdim for (N = GetSuccessorNode(N); N; N = GetSuccessorNode(N)) 91218887Sdim if (const Stmt *S = GetStmt(N->getLocation())) { 92218887Sdim // Check if the statement is '?' or '&&'/'||'. These are "merges", 93218887Sdim // not actual statement points. 94218887Sdim switch (S->getStmtClass()) { 95218887Sdim case Stmt::ChooseExprClass: 96218887Sdim case Stmt::BinaryConditionalOperatorClass: continue; 97218887Sdim case Stmt::ConditionalOperatorClass: continue; 98218887Sdim case Stmt::BinaryOperatorClass: { 99218887Sdim BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode(); 100218887Sdim if (Op == BO_LAnd || Op == BO_LOr) 101218887Sdim continue; 102218887Sdim break; 103218887Sdim } 104218887Sdim default: 105218887Sdim break; 106218887Sdim } 107218887Sdim 108218887Sdim // Some expressions don't have locations. 109218887Sdim if (S->getLocStart().isInvalid()) 110218887Sdim continue; 111218887Sdim 112218887Sdim return S; 113218887Sdim } 114218887Sdim 115218887Sdim return 0; 116218887Sdim} 117218887Sdim 118218887Sdimstatic inline const Stmt* 119218887SdimGetCurrentOrPreviousStmt(const ExplodedNode* N) { 120218887Sdim if (const Stmt *S = GetStmt(N->getLocation())) 121218887Sdim return S; 122218887Sdim 123218887Sdim return GetPreviousStmt(N); 124218887Sdim} 125218887Sdim 126218887Sdimstatic inline const Stmt* 127218887SdimGetCurrentOrNextStmt(const ExplodedNode* N) { 128218887Sdim if (const Stmt *S = GetStmt(N->getLocation())) 129218887Sdim return S; 130218887Sdim 131218887Sdim return GetNextStmt(N); 132218887Sdim} 133218887Sdim 134218887Sdim//===----------------------------------------------------------------------===// 135218887Sdim// PathDiagnosticBuilder and its associated routines and helper objects. 136218887Sdim//===----------------------------------------------------------------------===// 137218887Sdim 138218887Sdimtypedef llvm::DenseMap<const ExplodedNode*, 139218887Sdimconst ExplodedNode*> NodeBackMap; 140218887Sdim 141218887Sdimnamespace { 142218887Sdimclass NodeMapClosure : public BugReport::NodeResolver { 143218887Sdim NodeBackMap& M; 144218887Sdimpublic: 145218887Sdim NodeMapClosure(NodeBackMap *m) : M(*m) {} 146218887Sdim ~NodeMapClosure() {} 147218887Sdim 148218887Sdim const ExplodedNode* getOriginalNode(const ExplodedNode* N) { 149218887Sdim NodeBackMap::iterator I = M.find(N); 150218887Sdim return I == M.end() ? 0 : I->second; 151218887Sdim } 152218887Sdim}; 153218887Sdim 154218887Sdimclass PathDiagnosticBuilder : public BugReporterContext { 155218887Sdim BugReport *R; 156218887Sdim PathDiagnosticClient *PDC; 157218887Sdim llvm::OwningPtr<ParentMap> PM; 158218887Sdim NodeMapClosure NMC; 159218887Sdimpublic: 160218887Sdim PathDiagnosticBuilder(GRBugReporter &br, 161218887Sdim BugReport *r, NodeBackMap *Backmap, 162218887Sdim PathDiagnosticClient *pdc) 163218887Sdim : BugReporterContext(br), 164218887Sdim R(r), PDC(pdc), NMC(Backmap) { 165218887Sdim addVisitor(R); 166218887Sdim } 167218887Sdim 168218887Sdim PathDiagnosticLocation ExecutionContinues(const ExplodedNode* N); 169218887Sdim 170218887Sdim PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream& os, 171218887Sdim const ExplodedNode* N); 172218887Sdim 173218887Sdim Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); } 174218887Sdim 175218887Sdim ParentMap& getParentMap() { return R->getErrorNode()->getParentMap(); } 176218887Sdim 177218887Sdim const Stmt *getParent(const Stmt *S) { 178218887Sdim return getParentMap().getParent(S); 179218887Sdim } 180218887Sdim 181218887Sdim virtual NodeMapClosure& getNodeResolver() { return NMC; } 182218887Sdim 183218887Sdim PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S); 184218887Sdim 185218887Sdim PathDiagnosticClient::PathGenerationScheme getGenerationScheme() const { 186218887Sdim return PDC ? PDC->getGenerationScheme() : PathDiagnosticClient::Extensive; 187218887Sdim } 188218887Sdim 189218887Sdim bool supportsLogicalOpControlFlow() const { 190218887Sdim return PDC ? PDC->supportsLogicalOpControlFlow() : true; 191218887Sdim } 192218887Sdim}; 193218887Sdim} // end anonymous namespace 194218887Sdim 195218887SdimPathDiagnosticLocation 196218887SdimPathDiagnosticBuilder::ExecutionContinues(const ExplodedNode* N) { 197218887Sdim if (const Stmt *S = GetNextStmt(N)) 198218887Sdim return PathDiagnosticLocation(S, getSourceManager()); 199218887Sdim 200218887Sdim return FullSourceLoc(N->getLocationContext()->getDecl()->getBodyRBrace(), 201218887Sdim getSourceManager()); 202218887Sdim} 203218887Sdim 204218887SdimPathDiagnosticLocation 205218887SdimPathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream& os, 206218887Sdim const ExplodedNode* N) { 207218887Sdim 208218887Sdim // Slow, but probably doesn't matter. 209218887Sdim if (os.str().empty()) 210218887Sdim os << ' '; 211218887Sdim 212218887Sdim const PathDiagnosticLocation &Loc = ExecutionContinues(N); 213218887Sdim 214218887Sdim if (Loc.asStmt()) 215218887Sdim os << "Execution continues on line " 216218887Sdim << getSourceManager().getInstantiationLineNumber(Loc.asLocation()) 217218887Sdim << '.'; 218218887Sdim else { 219218887Sdim os << "Execution jumps to the end of the "; 220218887Sdim const Decl *D = N->getLocationContext()->getDecl(); 221218887Sdim if (isa<ObjCMethodDecl>(D)) 222218887Sdim os << "method"; 223218887Sdim else if (isa<FunctionDecl>(D)) 224218887Sdim os << "function"; 225218887Sdim else { 226218887Sdim assert(isa<BlockDecl>(D)); 227218887Sdim os << "anonymous block"; 228218887Sdim } 229218887Sdim os << '.'; 230218887Sdim } 231218887Sdim 232218887Sdim return Loc; 233218887Sdim} 234218887Sdim 235218887Sdimstatic bool IsNested(const Stmt *S, ParentMap &PM) { 236218887Sdim if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S))) 237218887Sdim return true; 238218887Sdim 239218887Sdim const Stmt *Parent = PM.getParentIgnoreParens(S); 240218887Sdim 241218887Sdim if (Parent) 242218887Sdim switch (Parent->getStmtClass()) { 243218887Sdim case Stmt::ForStmtClass: 244218887Sdim case Stmt::DoStmtClass: 245218887Sdim case Stmt::WhileStmtClass: 246218887Sdim return true; 247218887Sdim default: 248218887Sdim break; 249218887Sdim } 250218887Sdim 251218887Sdim return false; 252218887Sdim} 253218887Sdim 254218887SdimPathDiagnosticLocation 255218887SdimPathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { 256218887Sdim assert(S && "Null Stmt* passed to getEnclosingStmtLocation"); 257218887Sdim ParentMap &P = getParentMap(); 258218887Sdim SourceManager &SMgr = getSourceManager(); 259218887Sdim 260218887Sdim while (IsNested(S, P)) { 261218887Sdim const Stmt *Parent = P.getParentIgnoreParens(S); 262218887Sdim 263218887Sdim if (!Parent) 264218887Sdim break; 265218887Sdim 266218887Sdim switch (Parent->getStmtClass()) { 267218887Sdim case Stmt::BinaryOperatorClass: { 268218887Sdim const BinaryOperator *B = cast<BinaryOperator>(Parent); 269218887Sdim if (B->isLogicalOp()) 270218887Sdim return PathDiagnosticLocation(S, SMgr); 271218887Sdim break; 272218887Sdim } 273218887Sdim case Stmt::CompoundStmtClass: 274218887Sdim case Stmt::StmtExprClass: 275218887Sdim return PathDiagnosticLocation(S, SMgr); 276218887Sdim case Stmt::ChooseExprClass: 277218887Sdim // Similar to '?' if we are referring to condition, just have the edge 278218887Sdim // point to the entire choose expression. 279218887Sdim if (cast<ChooseExpr>(Parent)->getCond() == S) 280218887Sdim return PathDiagnosticLocation(Parent, SMgr); 281218887Sdim else 282218887Sdim return PathDiagnosticLocation(S, SMgr); 283218887Sdim case Stmt::BinaryConditionalOperatorClass: 284218887Sdim case Stmt::ConditionalOperatorClass: 285218887Sdim // For '?', if we are referring to condition, just have the edge point 286218887Sdim // to the entire '?' expression. 287218887Sdim if (cast<AbstractConditionalOperator>(Parent)->getCond() == S) 288218887Sdim return PathDiagnosticLocation(Parent, SMgr); 289218887Sdim else 290218887Sdim return PathDiagnosticLocation(S, SMgr); 291218887Sdim case Stmt::DoStmtClass: 292218887Sdim return PathDiagnosticLocation(S, SMgr); 293218887Sdim case Stmt::ForStmtClass: 294218887Sdim if (cast<ForStmt>(Parent)->getBody() == S) 295218887Sdim return PathDiagnosticLocation(S, SMgr); 296218887Sdim break; 297218887Sdim case Stmt::IfStmtClass: 298218887Sdim if (cast<IfStmt>(Parent)->getCond() != S) 299218887Sdim return PathDiagnosticLocation(S, SMgr); 300218887Sdim break; 301218887Sdim case Stmt::ObjCForCollectionStmtClass: 302218887Sdim if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S) 303218887Sdim return PathDiagnosticLocation(S, SMgr); 304218887Sdim break; 305218887Sdim case Stmt::WhileStmtClass: 306218887Sdim if (cast<WhileStmt>(Parent)->getCond() != S) 307218887Sdim return PathDiagnosticLocation(S, SMgr); 308218887Sdim break; 309218887Sdim default: 310218887Sdim break; 311218887Sdim } 312218887Sdim 313218887Sdim S = Parent; 314218887Sdim } 315218887Sdim 316218887Sdim assert(S && "Cannot have null Stmt for PathDiagnosticLocation"); 317218887Sdim 318218887Sdim // Special case: DeclStmts can appear in for statement declarations, in which 319218887Sdim // case the ForStmt is the context. 320218887Sdim if (isa<DeclStmt>(S)) { 321218887Sdim if (const Stmt *Parent = P.getParent(S)) { 322218887Sdim switch (Parent->getStmtClass()) { 323218887Sdim case Stmt::ForStmtClass: 324218887Sdim case Stmt::ObjCForCollectionStmtClass: 325218887Sdim return PathDiagnosticLocation(Parent, SMgr); 326218887Sdim default: 327218887Sdim break; 328218887Sdim } 329218887Sdim } 330218887Sdim } 331218887Sdim else if (isa<BinaryOperator>(S)) { 332218887Sdim // Special case: the binary operator represents the initialization 333218887Sdim // code in a for statement (this can happen when the variable being 334218887Sdim // initialized is an old variable. 335218887Sdim if (const ForStmt *FS = 336218887Sdim dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) { 337218887Sdim if (FS->getInit() == S) 338218887Sdim return PathDiagnosticLocation(FS, SMgr); 339218887Sdim } 340218887Sdim } 341218887Sdim 342218887Sdim return PathDiagnosticLocation(S, SMgr); 343218887Sdim} 344218887Sdim 345218887Sdim//===----------------------------------------------------------------------===// 346218887Sdim// ScanNotableSymbols: closure-like callback for scanning Store bindings. 347218887Sdim//===----------------------------------------------------------------------===// 348218887Sdim 349218887Sdimstatic const VarDecl* 350218887SdimGetMostRecentVarDeclBinding(const ExplodedNode* N, 351218887Sdim GRStateManager& VMgr, SVal X) { 352218887Sdim 353218887Sdim for ( ; N ; N = N->pred_empty() ? 0 : *N->pred_begin()) { 354218887Sdim 355218887Sdim ProgramPoint P = N->getLocation(); 356218887Sdim 357218887Sdim if (!isa<PostStmt>(P)) 358218887Sdim continue; 359218887Sdim 360218887Sdim const DeclRefExpr* DR = dyn_cast<DeclRefExpr>(cast<PostStmt>(P).getStmt()); 361218887Sdim 362218887Sdim if (!DR) 363218887Sdim continue; 364218887Sdim 365218887Sdim SVal Y = N->getState()->getSVal(DR); 366218887Sdim 367218887Sdim if (X != Y) 368218887Sdim continue; 369218887Sdim 370218887Sdim const VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()); 371218887Sdim 372218887Sdim if (!VD) 373218887Sdim continue; 374218887Sdim 375218887Sdim return VD; 376218887Sdim } 377218887Sdim 378218887Sdim return 0; 379218887Sdim} 380218887Sdim 381218887Sdimnamespace { 382218887Sdimclass NotableSymbolHandler 383218887Sdim: public StoreManager::BindingsHandler { 384218887Sdim 385218887Sdim SymbolRef Sym; 386218887Sdim const GRState* PrevSt; 387218887Sdim const Stmt* S; 388218887Sdim GRStateManager& VMgr; 389218887Sdim const ExplodedNode* Pred; 390218887Sdim PathDiagnostic& PD; 391218887Sdim BugReporter& BR; 392218887Sdim 393218887Sdimpublic: 394218887Sdim 395218887Sdim NotableSymbolHandler(SymbolRef sym, const GRState* prevst, const Stmt* s, 396218887Sdim GRStateManager& vmgr, const ExplodedNode* pred, 397218887Sdim PathDiagnostic& pd, BugReporter& br) 398218887Sdim : Sym(sym), PrevSt(prevst), S(s), VMgr(vmgr), Pred(pred), PD(pd), BR(br) {} 399218887Sdim 400218887Sdim bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R, 401218887Sdim SVal V) { 402218887Sdim 403218887Sdim SymbolRef ScanSym = V.getAsSymbol(); 404218887Sdim 405218887Sdim if (ScanSym != Sym) 406218887Sdim return true; 407218887Sdim 408218887Sdim // Check if the previous state has this binding. 409218887Sdim SVal X = PrevSt->getSVal(loc::MemRegionVal(R)); 410218887Sdim 411218887Sdim if (X == V) // Same binding? 412218887Sdim return true; 413218887Sdim 414218887Sdim // Different binding. Only handle assignments for now. We don't pull 415218887Sdim // this check out of the loop because we will eventually handle other 416218887Sdim // cases. 417218887Sdim 418218887Sdim VarDecl *VD = 0; 419218887Sdim 420218887Sdim if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 421218887Sdim if (!B->isAssignmentOp()) 422218887Sdim return true; 423218887Sdim 424218887Sdim // What variable did we assign to? 425218887Sdim DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts()); 426218887Sdim 427218887Sdim if (!DR) 428218887Sdim return true; 429218887Sdim 430218887Sdim VD = dyn_cast<VarDecl>(DR->getDecl()); 431218887Sdim } 432218887Sdim else if (const DeclStmt* DS = dyn_cast<DeclStmt>(S)) { 433218887Sdim // FIXME: Eventually CFGs won't have DeclStmts. Right now we 434218887Sdim // assume that each DeclStmt has a single Decl. This invariant 435218887Sdim // holds by contruction in the CFG. 436218887Sdim VD = dyn_cast<VarDecl>(*DS->decl_begin()); 437218887Sdim } 438218887Sdim 439218887Sdim if (!VD) 440218887Sdim return true; 441218887Sdim 442218887Sdim // What is the most recently referenced variable with this binding? 443218887Sdim const VarDecl* MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V); 444218887Sdim 445218887Sdim if (!MostRecent) 446218887Sdim return true; 447218887Sdim 448218887Sdim // Create the diagnostic. 449218887Sdim FullSourceLoc L(S->getLocStart(), BR.getSourceManager()); 450218887Sdim 451218887Sdim if (Loc::isLocType(VD->getType())) { 452218887Sdim std::string msg = "'" + std::string(VD->getNameAsString()) + 453218887Sdim "' now aliases '" + MostRecent->getNameAsString() + "'"; 454218887Sdim 455218887Sdim PD.push_front(new PathDiagnosticEventPiece(L, msg)); 456218887Sdim } 457218887Sdim 458218887Sdim return true; 459218887Sdim } 460218887Sdim}; 461218887Sdim} 462218887Sdim 463218887Sdimstatic void HandleNotableSymbol(const ExplodedNode* N, 464218887Sdim const Stmt* S, 465218887Sdim SymbolRef Sym, BugReporter& BR, 466218887Sdim PathDiagnostic& PD) { 467218887Sdim 468218887Sdim const ExplodedNode* Pred = N->pred_empty() ? 0 : *N->pred_begin(); 469218887Sdim const GRState* PrevSt = Pred ? Pred->getState() : 0; 470218887Sdim 471218887Sdim if (!PrevSt) 472218887Sdim return; 473218887Sdim 474218887Sdim // Look at the region bindings of the current state that map to the 475218887Sdim // specified symbol. Are any of them not in the previous state? 476218887Sdim GRStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager(); 477218887Sdim NotableSymbolHandler H(Sym, PrevSt, S, VMgr, Pred, PD, BR); 478218887Sdim cast<GRBugReporter>(BR).getStateManager().iterBindings(N->getState(), H); 479218887Sdim} 480218887Sdim 481218887Sdimnamespace { 482218887Sdimclass ScanNotableSymbols 483218887Sdim: public StoreManager::BindingsHandler { 484218887Sdim 485218887Sdim llvm::SmallSet<SymbolRef, 10> AlreadyProcessed; 486218887Sdim const ExplodedNode* N; 487218887Sdim const Stmt* S; 488218887Sdim GRBugReporter& BR; 489218887Sdim PathDiagnostic& PD; 490218887Sdim 491218887Sdimpublic: 492218887Sdim ScanNotableSymbols(const ExplodedNode* n, const Stmt* s, 493218887Sdim GRBugReporter& br, PathDiagnostic& pd) 494218887Sdim : N(n), S(s), BR(br), PD(pd) {} 495218887Sdim 496218887Sdim bool HandleBinding(StoreManager& SMgr, Store store, 497218887Sdim const MemRegion* R, SVal V) { 498218887Sdim 499218887Sdim SymbolRef ScanSym = V.getAsSymbol(); 500218887Sdim 501218887Sdim if (!ScanSym) 502218887Sdim return true; 503218887Sdim 504218887Sdim if (!BR.isNotable(ScanSym)) 505218887Sdim return true; 506218887Sdim 507218887Sdim if (AlreadyProcessed.count(ScanSym)) 508218887Sdim return true; 509218887Sdim 510218887Sdim AlreadyProcessed.insert(ScanSym); 511218887Sdim 512218887Sdim HandleNotableSymbol(N, S, ScanSym, BR, PD); 513218887Sdim return true; 514218887Sdim } 515218887Sdim}; 516218887Sdim} // end anonymous namespace 517218887Sdim 518218887Sdim//===----------------------------------------------------------------------===// 519218887Sdim// "Minimal" path diagnostic generation algorithm. 520218887Sdim//===----------------------------------------------------------------------===// 521218887Sdim 522218887Sdimstatic void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM); 523218887Sdim 524218887Sdimstatic void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, 525218887Sdim PathDiagnosticBuilder &PDB, 526218887Sdim const ExplodedNode *N) { 527218887Sdim 528218887Sdim SourceManager& SMgr = PDB.getSourceManager(); 529218887Sdim const ExplodedNode* NextNode = N->pred_empty() 530218887Sdim ? NULL : *(N->pred_begin()); 531218887Sdim while (NextNode) { 532218887Sdim N = NextNode; 533218887Sdim NextNode = GetPredecessorNode(N); 534218887Sdim 535218887Sdim ProgramPoint P = N->getLocation(); 536218887Sdim 537218887Sdim if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P)) { 538218887Sdim const CFGBlock* Src = BE->getSrc(); 539218887Sdim const CFGBlock* Dst = BE->getDst(); 540218887Sdim const Stmt* T = Src->getTerminator(); 541218887Sdim 542218887Sdim if (!T) 543218887Sdim continue; 544218887Sdim 545218887Sdim FullSourceLoc Start(T->getLocStart(), SMgr); 546218887Sdim 547218887Sdim switch (T->getStmtClass()) { 548218887Sdim default: 549218887Sdim break; 550218887Sdim 551218887Sdim case Stmt::GotoStmtClass: 552218887Sdim case Stmt::IndirectGotoStmtClass: { 553218887Sdim const Stmt* S = GetNextStmt(N); 554218887Sdim 555218887Sdim if (!S) 556218887Sdim continue; 557218887Sdim 558218887Sdim std::string sbuf; 559218887Sdim llvm::raw_string_ostream os(sbuf); 560218887Sdim const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S); 561218887Sdim 562218887Sdim os << "Control jumps to line " 563218887Sdim << End.asLocation().getInstantiationLineNumber(); 564218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 565218887Sdim os.str())); 566218887Sdim break; 567218887Sdim } 568218887Sdim 569218887Sdim case Stmt::SwitchStmtClass: { 570218887Sdim // Figure out what case arm we took. 571218887Sdim std::string sbuf; 572218887Sdim llvm::raw_string_ostream os(sbuf); 573218887Sdim 574218887Sdim if (const Stmt* S = Dst->getLabel()) { 575218887Sdim PathDiagnosticLocation End(S, SMgr); 576218887Sdim 577218887Sdim switch (S->getStmtClass()) { 578218887Sdim default: 579218887Sdim os << "No cases match in the switch statement. " 580218887Sdim "Control jumps to line " 581218887Sdim << End.asLocation().getInstantiationLineNumber(); 582218887Sdim break; 583218887Sdim case Stmt::DefaultStmtClass: 584218887Sdim os << "Control jumps to the 'default' case at line " 585218887Sdim << End.asLocation().getInstantiationLineNumber(); 586218887Sdim break; 587218887Sdim 588218887Sdim case Stmt::CaseStmtClass: { 589218887Sdim os << "Control jumps to 'case "; 590218887Sdim const CaseStmt* Case = cast<CaseStmt>(S); 591218887Sdim const Expr* LHS = Case->getLHS()->IgnoreParenCasts(); 592218887Sdim 593218887Sdim // Determine if it is an enum. 594218887Sdim bool GetRawInt = true; 595218887Sdim 596218887Sdim if (const DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) { 597218887Sdim // FIXME: Maybe this should be an assertion. Are there cases 598218887Sdim // were it is not an EnumConstantDecl? 599218887Sdim const EnumConstantDecl* D = 600218887Sdim dyn_cast<EnumConstantDecl>(DR->getDecl()); 601218887Sdim 602218887Sdim if (D) { 603218887Sdim GetRawInt = false; 604218887Sdim os << D; 605218887Sdim } 606218887Sdim } 607218887Sdim 608218887Sdim if (GetRawInt) 609218887Sdim os << LHS->EvaluateAsInt(PDB.getASTContext()); 610218887Sdim 611218887Sdim os << ":' at line " 612218887Sdim << End.asLocation().getInstantiationLineNumber(); 613218887Sdim break; 614218887Sdim } 615218887Sdim } 616218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 617218887Sdim os.str())); 618218887Sdim } 619218887Sdim else { 620218887Sdim os << "'Default' branch taken. "; 621218887Sdim const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N); 622218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 623218887Sdim os.str())); 624218887Sdim } 625218887Sdim 626218887Sdim break; 627218887Sdim } 628218887Sdim 629218887Sdim case Stmt::BreakStmtClass: 630218887Sdim case Stmt::ContinueStmtClass: { 631218887Sdim std::string sbuf; 632218887Sdim llvm::raw_string_ostream os(sbuf); 633218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 634218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 635218887Sdim os.str())); 636218887Sdim break; 637218887Sdim } 638218887Sdim 639218887Sdim // Determine control-flow for ternary '?'. 640218887Sdim case Stmt::BinaryConditionalOperatorClass: 641218887Sdim case Stmt::ConditionalOperatorClass: { 642218887Sdim std::string sbuf; 643218887Sdim llvm::raw_string_ostream os(sbuf); 644218887Sdim os << "'?' condition is "; 645218887Sdim 646218887Sdim if (*(Src->succ_begin()+1) == Dst) 647218887Sdim os << "false"; 648218887Sdim else 649218887Sdim os << "true"; 650218887Sdim 651218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 652218887Sdim 653218887Sdim if (const Stmt *S = End.asStmt()) 654218887Sdim End = PDB.getEnclosingStmtLocation(S); 655218887Sdim 656218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 657218887Sdim os.str())); 658218887Sdim break; 659218887Sdim } 660218887Sdim 661218887Sdim // Determine control-flow for short-circuited '&&' and '||'. 662218887Sdim case Stmt::BinaryOperatorClass: { 663218887Sdim if (!PDB.supportsLogicalOpControlFlow()) 664218887Sdim break; 665218887Sdim 666218887Sdim const BinaryOperator *B = cast<BinaryOperator>(T); 667218887Sdim std::string sbuf; 668218887Sdim llvm::raw_string_ostream os(sbuf); 669218887Sdim os << "Left side of '"; 670218887Sdim 671218887Sdim if (B->getOpcode() == BO_LAnd) { 672218887Sdim os << "&&" << "' is "; 673218887Sdim 674218887Sdim if (*(Src->succ_begin()+1) == Dst) { 675218887Sdim os << "false"; 676218887Sdim PathDiagnosticLocation End(B->getLHS(), SMgr); 677218887Sdim PathDiagnosticLocation Start(B->getOperatorLoc(), SMgr); 678218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 679218887Sdim os.str())); 680218887Sdim } 681218887Sdim else { 682218887Sdim os << "true"; 683218887Sdim PathDiagnosticLocation Start(B->getLHS(), SMgr); 684218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 685218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 686218887Sdim os.str())); 687218887Sdim } 688218887Sdim } 689218887Sdim else { 690218887Sdim assert(B->getOpcode() == BO_LOr); 691218887Sdim os << "||" << "' is "; 692218887Sdim 693218887Sdim if (*(Src->succ_begin()+1) == Dst) { 694218887Sdim os << "false"; 695218887Sdim PathDiagnosticLocation Start(B->getLHS(), SMgr); 696218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 697218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 698218887Sdim os.str())); 699218887Sdim } 700218887Sdim else { 701218887Sdim os << "true"; 702218887Sdim PathDiagnosticLocation End(B->getLHS(), SMgr); 703218887Sdim PathDiagnosticLocation Start(B->getOperatorLoc(), SMgr); 704218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 705218887Sdim os.str())); 706218887Sdim } 707218887Sdim } 708218887Sdim 709218887Sdim break; 710218887Sdim } 711218887Sdim 712218887Sdim case Stmt::DoStmtClass: { 713218887Sdim if (*(Src->succ_begin()) == Dst) { 714218887Sdim std::string sbuf; 715218887Sdim llvm::raw_string_ostream os(sbuf); 716218887Sdim 717218887Sdim os << "Loop condition is true. "; 718218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 719218887Sdim 720218887Sdim if (const Stmt *S = End.asStmt()) 721218887Sdim End = PDB.getEnclosingStmtLocation(S); 722218887Sdim 723218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 724218887Sdim os.str())); 725218887Sdim } 726218887Sdim else { 727218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 728218887Sdim 729218887Sdim if (const Stmt *S = End.asStmt()) 730218887Sdim End = PDB.getEnclosingStmtLocation(S); 731218887Sdim 732218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 733218887Sdim "Loop condition is false. Exiting loop")); 734218887Sdim } 735218887Sdim 736218887Sdim break; 737218887Sdim } 738218887Sdim 739218887Sdim case Stmt::WhileStmtClass: 740218887Sdim case Stmt::ForStmtClass: { 741218887Sdim if (*(Src->succ_begin()+1) == Dst) { 742218887Sdim std::string sbuf; 743218887Sdim llvm::raw_string_ostream os(sbuf); 744218887Sdim 745218887Sdim os << "Loop condition is false. "; 746218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 747218887Sdim if (const Stmt *S = End.asStmt()) 748218887Sdim End = PDB.getEnclosingStmtLocation(S); 749218887Sdim 750218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 751218887Sdim os.str())); 752218887Sdim } 753218887Sdim else { 754218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 755218887Sdim if (const Stmt *S = End.asStmt()) 756218887Sdim End = PDB.getEnclosingStmtLocation(S); 757218887Sdim 758218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 759218887Sdim "Loop condition is true. Entering loop body")); 760218887Sdim } 761218887Sdim 762218887Sdim break; 763218887Sdim } 764218887Sdim 765218887Sdim case Stmt::IfStmtClass: { 766218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 767218887Sdim 768218887Sdim if (const Stmt *S = End.asStmt()) 769218887Sdim End = PDB.getEnclosingStmtLocation(S); 770218887Sdim 771218887Sdim if (*(Src->succ_begin()+1) == Dst) 772218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 773218887Sdim "Taking false branch")); 774218887Sdim else 775218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(Start, End, 776218887Sdim "Taking true branch")); 777218887Sdim 778218887Sdim break; 779218887Sdim } 780218887Sdim } 781218887Sdim } 782218887Sdim 783218887Sdim if (NextNode) { 784218887Sdim for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(), 785218887Sdim E = PDB.visitor_end(); I!=E; ++I) { 786218887Sdim if (PathDiagnosticPiece* p = (*I)->VisitNode(N, NextNode, PDB)) 787218887Sdim PD.push_front(p); 788218887Sdim } 789218887Sdim } 790218887Sdim 791218887Sdim if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) { 792218887Sdim // Scan the region bindings, and see if a "notable" symbol has a new 793218887Sdim // lval binding. 794218887Sdim ScanNotableSymbols SNS(N, PS->getStmt(), PDB.getBugReporter(), PD); 795218887Sdim PDB.getStateManager().iterBindings(N->getState(), SNS); 796218887Sdim } 797218887Sdim } 798218887Sdim 799218887Sdim // After constructing the full PathDiagnostic, do a pass over it to compact 800218887Sdim // PathDiagnosticPieces that occur within a macro. 801218887Sdim CompactPathDiagnostic(PD, PDB.getSourceManager()); 802218887Sdim} 803218887Sdim 804218887Sdim//===----------------------------------------------------------------------===// 805218887Sdim// "Extensive" PathDiagnostic generation. 806218887Sdim//===----------------------------------------------------------------------===// 807218887Sdim 808218887Sdimstatic bool IsControlFlowExpr(const Stmt *S) { 809218887Sdim const Expr *E = dyn_cast<Expr>(S); 810218887Sdim 811218887Sdim if (!E) 812218887Sdim return false; 813218887Sdim 814218887Sdim E = E->IgnoreParenCasts(); 815218887Sdim 816218887Sdim if (isa<AbstractConditionalOperator>(E)) 817218887Sdim return true; 818218887Sdim 819218887Sdim if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E)) 820218887Sdim if (B->isLogicalOp()) 821218887Sdim return true; 822218887Sdim 823218887Sdim return false; 824218887Sdim} 825218887Sdim 826218887Sdimnamespace { 827218887Sdimclass ContextLocation : public PathDiagnosticLocation { 828218887Sdim bool IsDead; 829218887Sdimpublic: 830218887Sdim ContextLocation(const PathDiagnosticLocation &L, bool isdead = false) 831218887Sdim : PathDiagnosticLocation(L), IsDead(isdead) {} 832218887Sdim 833218887Sdim void markDead() { IsDead = true; } 834218887Sdim bool isDead() const { return IsDead; } 835218887Sdim}; 836218887Sdim 837218887Sdimclass EdgeBuilder { 838218887Sdim std::vector<ContextLocation> CLocs; 839218887Sdim typedef std::vector<ContextLocation>::iterator iterator; 840218887Sdim PathDiagnostic &PD; 841218887Sdim PathDiagnosticBuilder &PDB; 842218887Sdim PathDiagnosticLocation PrevLoc; 843218887Sdim 844218887Sdim bool IsConsumedExpr(const PathDiagnosticLocation &L); 845218887Sdim 846218887Sdim bool containsLocation(const PathDiagnosticLocation &Container, 847218887Sdim const PathDiagnosticLocation &Containee); 848218887Sdim 849218887Sdim PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L); 850218887Sdim 851218887Sdim PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L, 852218887Sdim bool firstCharOnly = false) { 853218887Sdim if (const Stmt *S = L.asStmt()) { 854218887Sdim const Stmt *Original = S; 855218887Sdim while (1) { 856218887Sdim // Adjust the location for some expressions that are best referenced 857218887Sdim // by one of their subexpressions. 858218887Sdim switch (S->getStmtClass()) { 859218887Sdim default: 860218887Sdim break; 861218887Sdim case Stmt::ParenExprClass: 862218887Sdim S = cast<ParenExpr>(S)->IgnoreParens(); 863218887Sdim firstCharOnly = true; 864218887Sdim continue; 865218887Sdim case Stmt::BinaryConditionalOperatorClass: 866218887Sdim case Stmt::ConditionalOperatorClass: 867218887Sdim S = cast<AbstractConditionalOperator>(S)->getCond(); 868218887Sdim firstCharOnly = true; 869218887Sdim continue; 870218887Sdim case Stmt::ChooseExprClass: 871218887Sdim S = cast<ChooseExpr>(S)->getCond(); 872218887Sdim firstCharOnly = true; 873218887Sdim continue; 874218887Sdim case Stmt::BinaryOperatorClass: 875218887Sdim S = cast<BinaryOperator>(S)->getLHS(); 876218887Sdim firstCharOnly = true; 877218887Sdim continue; 878218887Sdim } 879218887Sdim 880218887Sdim break; 881218887Sdim } 882218887Sdim 883218887Sdim if (S != Original) 884218887Sdim L = PathDiagnosticLocation(S, L.getManager()); 885218887Sdim } 886218887Sdim 887218887Sdim if (firstCharOnly) 888218887Sdim L = PathDiagnosticLocation(L.asLocation()); 889218887Sdim 890218887Sdim return L; 891218887Sdim } 892218887Sdim 893218887Sdim void popLocation() { 894218887Sdim if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) { 895218887Sdim // For contexts, we only one the first character as the range. 896218887Sdim rawAddEdge(cleanUpLocation(CLocs.back(), true)); 897218887Sdim } 898218887Sdim CLocs.pop_back(); 899218887Sdim } 900218887Sdim 901218887Sdimpublic: 902218887Sdim EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb) 903218887Sdim : PD(pd), PDB(pdb) { 904218887Sdim 905218887Sdim // If the PathDiagnostic already has pieces, add the enclosing statement 906218887Sdim // of the first piece as a context as well. 907218887Sdim if (!PD.empty()) { 908218887Sdim PrevLoc = PD.begin()->getLocation(); 909218887Sdim 910218887Sdim if (const Stmt *S = PrevLoc.asStmt()) 911218887Sdim addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 912218887Sdim } 913218887Sdim } 914218887Sdim 915218887Sdim ~EdgeBuilder() { 916218887Sdim while (!CLocs.empty()) popLocation(); 917218887Sdim 918218887Sdim // Finally, add an initial edge from the start location of the first 919218887Sdim // statement (if it doesn't already exist). 920218887Sdim // FIXME: Should handle CXXTryStmt if analyser starts supporting C++. 921218887Sdim if (const CompoundStmt *CS = 922218887Sdim dyn_cast_or_null<CompoundStmt>(PDB.getCodeDecl().getBody())) 923218887Sdim if (!CS->body_empty()) { 924218887Sdim SourceLocation Loc = (*CS->body_begin())->getLocStart(); 925218887Sdim rawAddEdge(PathDiagnosticLocation(Loc, PDB.getSourceManager())); 926218887Sdim } 927218887Sdim 928218887Sdim } 929218887Sdim 930218887Sdim void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false); 931218887Sdim 932218887Sdim void rawAddEdge(PathDiagnosticLocation NewLoc); 933218887Sdim 934218887Sdim void addContext(const Stmt *S); 935218887Sdim void addExtendedContext(const Stmt *S); 936218887Sdim}; 937218887Sdim} // end anonymous namespace 938218887Sdim 939218887Sdim 940218887SdimPathDiagnosticLocation 941218887SdimEdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) { 942218887Sdim if (const Stmt *S = L.asStmt()) { 943218887Sdim if (IsControlFlowExpr(S)) 944218887Sdim return L; 945218887Sdim 946218887Sdim return PDB.getEnclosingStmtLocation(S); 947218887Sdim } 948218887Sdim 949218887Sdim return L; 950218887Sdim} 951218887Sdim 952218887Sdimbool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container, 953218887Sdim const PathDiagnosticLocation &Containee) { 954218887Sdim 955218887Sdim if (Container == Containee) 956218887Sdim return true; 957218887Sdim 958218887Sdim if (Container.asDecl()) 959218887Sdim return true; 960218887Sdim 961218887Sdim if (const Stmt *S = Containee.asStmt()) 962218887Sdim if (const Stmt *ContainerS = Container.asStmt()) { 963218887Sdim while (S) { 964218887Sdim if (S == ContainerS) 965218887Sdim return true; 966218887Sdim S = PDB.getParent(S); 967218887Sdim } 968218887Sdim return false; 969218887Sdim } 970218887Sdim 971218887Sdim // Less accurate: compare using source ranges. 972218887Sdim SourceRange ContainerR = Container.asRange(); 973218887Sdim SourceRange ContaineeR = Containee.asRange(); 974218887Sdim 975218887Sdim SourceManager &SM = PDB.getSourceManager(); 976218887Sdim SourceLocation ContainerRBeg = SM.getInstantiationLoc(ContainerR.getBegin()); 977218887Sdim SourceLocation ContainerREnd = SM.getInstantiationLoc(ContainerR.getEnd()); 978218887Sdim SourceLocation ContaineeRBeg = SM.getInstantiationLoc(ContaineeR.getBegin()); 979218887Sdim SourceLocation ContaineeREnd = SM.getInstantiationLoc(ContaineeR.getEnd()); 980218887Sdim 981218887Sdim unsigned ContainerBegLine = SM.getInstantiationLineNumber(ContainerRBeg); 982218887Sdim unsigned ContainerEndLine = SM.getInstantiationLineNumber(ContainerREnd); 983218887Sdim unsigned ContaineeBegLine = SM.getInstantiationLineNumber(ContaineeRBeg); 984218887Sdim unsigned ContaineeEndLine = SM.getInstantiationLineNumber(ContaineeREnd); 985218887Sdim 986218887Sdim assert(ContainerBegLine <= ContainerEndLine); 987218887Sdim assert(ContaineeBegLine <= ContaineeEndLine); 988218887Sdim 989218887Sdim return (ContainerBegLine <= ContaineeBegLine && 990218887Sdim ContainerEndLine >= ContaineeEndLine && 991218887Sdim (ContainerBegLine != ContaineeBegLine || 992218887Sdim SM.getInstantiationColumnNumber(ContainerRBeg) <= 993218887Sdim SM.getInstantiationColumnNumber(ContaineeRBeg)) && 994218887Sdim (ContainerEndLine != ContaineeEndLine || 995218887Sdim SM.getInstantiationColumnNumber(ContainerREnd) >= 996218887Sdim SM.getInstantiationColumnNumber(ContainerREnd))); 997218887Sdim} 998218887Sdim 999218887Sdimvoid EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) { 1000218887Sdim if (!PrevLoc.isValid()) { 1001218887Sdim PrevLoc = NewLoc; 1002218887Sdim return; 1003218887Sdim } 1004218887Sdim 1005218887Sdim const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc); 1006218887Sdim const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc); 1007218887Sdim 1008218887Sdim if (NewLocClean.asLocation() == PrevLocClean.asLocation()) 1009218887Sdim return; 1010218887Sdim 1011218887Sdim // FIXME: Ignore intra-macro edges for now. 1012218887Sdim if (NewLocClean.asLocation().getInstantiationLoc() == 1013218887Sdim PrevLocClean.asLocation().getInstantiationLoc()) 1014218887Sdim return; 1015218887Sdim 1016218887Sdim PD.push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean)); 1017218887Sdim PrevLoc = NewLoc; 1018218887Sdim} 1019218887Sdim 1020218887Sdimvoid EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd) { 1021218887Sdim 1022218887Sdim if (!alwaysAdd && NewLoc.asLocation().isMacroID()) 1023218887Sdim return; 1024218887Sdim 1025218887Sdim const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc); 1026218887Sdim 1027218887Sdim while (!CLocs.empty()) { 1028218887Sdim ContextLocation &TopContextLoc = CLocs.back(); 1029218887Sdim 1030218887Sdim // Is the top location context the same as the one for the new location? 1031218887Sdim if (TopContextLoc == CLoc) { 1032218887Sdim if (alwaysAdd) { 1033218887Sdim if (IsConsumedExpr(TopContextLoc) && 1034218887Sdim !IsControlFlowExpr(TopContextLoc.asStmt())) 1035218887Sdim TopContextLoc.markDead(); 1036218887Sdim 1037218887Sdim rawAddEdge(NewLoc); 1038218887Sdim } 1039218887Sdim 1040218887Sdim return; 1041218887Sdim } 1042218887Sdim 1043218887Sdim if (containsLocation(TopContextLoc, CLoc)) { 1044218887Sdim if (alwaysAdd) { 1045218887Sdim rawAddEdge(NewLoc); 1046218887Sdim 1047218887Sdim if (IsConsumedExpr(CLoc) && !IsControlFlowExpr(CLoc.asStmt())) { 1048218887Sdim CLocs.push_back(ContextLocation(CLoc, true)); 1049218887Sdim return; 1050218887Sdim } 1051218887Sdim } 1052218887Sdim 1053218887Sdim CLocs.push_back(CLoc); 1054218887Sdim return; 1055218887Sdim } 1056218887Sdim 1057218887Sdim // Context does not contain the location. Flush it. 1058218887Sdim popLocation(); 1059218887Sdim } 1060218887Sdim 1061218887Sdim // If we reach here, there is no enclosing context. Just add the edge. 1062218887Sdim rawAddEdge(NewLoc); 1063218887Sdim} 1064218887Sdim 1065218887Sdimbool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) { 1066218887Sdim if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt())) 1067218887Sdim return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X); 1068218887Sdim 1069218887Sdim return false; 1070218887Sdim} 1071218887Sdim 1072218887Sdimvoid EdgeBuilder::addExtendedContext(const Stmt *S) { 1073218887Sdim if (!S) 1074218887Sdim return; 1075218887Sdim 1076218887Sdim const Stmt *Parent = PDB.getParent(S); 1077218887Sdim while (Parent) { 1078218887Sdim if (isa<CompoundStmt>(Parent)) 1079218887Sdim Parent = PDB.getParent(Parent); 1080218887Sdim else 1081218887Sdim break; 1082218887Sdim } 1083218887Sdim 1084218887Sdim if (Parent) { 1085218887Sdim switch (Parent->getStmtClass()) { 1086218887Sdim case Stmt::DoStmtClass: 1087218887Sdim case Stmt::ObjCAtSynchronizedStmtClass: 1088218887Sdim addContext(Parent); 1089218887Sdim default: 1090218887Sdim break; 1091218887Sdim } 1092218887Sdim } 1093218887Sdim 1094218887Sdim addContext(S); 1095218887Sdim} 1096218887Sdim 1097218887Sdimvoid EdgeBuilder::addContext(const Stmt *S) { 1098218887Sdim if (!S) 1099218887Sdim return; 1100218887Sdim 1101218887Sdim PathDiagnosticLocation L(S, PDB.getSourceManager()); 1102218887Sdim 1103218887Sdim while (!CLocs.empty()) { 1104218887Sdim const PathDiagnosticLocation &TopContextLoc = CLocs.back(); 1105218887Sdim 1106218887Sdim // Is the top location context the same as the one for the new location? 1107218887Sdim if (TopContextLoc == L) 1108218887Sdim return; 1109218887Sdim 1110218887Sdim if (containsLocation(TopContextLoc, L)) { 1111218887Sdim CLocs.push_back(L); 1112218887Sdim return; 1113218887Sdim } 1114218887Sdim 1115218887Sdim // Context does not contain the location. Flush it. 1116218887Sdim popLocation(); 1117218887Sdim } 1118218887Sdim 1119218887Sdim CLocs.push_back(L); 1120218887Sdim} 1121218887Sdim 1122218887Sdimstatic void GenerateExtensivePathDiagnostic(PathDiagnostic& PD, 1123218887Sdim PathDiagnosticBuilder &PDB, 1124218887Sdim const ExplodedNode *N) { 1125218887Sdim EdgeBuilder EB(PD, PDB); 1126218887Sdim 1127218887Sdim const ExplodedNode* NextNode = N->pred_empty() ? NULL : *(N->pred_begin()); 1128218887Sdim while (NextNode) { 1129218887Sdim N = NextNode; 1130218887Sdim NextNode = GetPredecessorNode(N); 1131218887Sdim ProgramPoint P = N->getLocation(); 1132218887Sdim 1133218887Sdim do { 1134218887Sdim // Block edges. 1135218887Sdim if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { 1136218887Sdim const CFGBlock &Blk = *BE->getSrc(); 1137218887Sdim const Stmt *Term = Blk.getTerminator(); 1138218887Sdim 1139218887Sdim // Are we jumping to the head of a loop? Add a special diagnostic. 1140218887Sdim if (const Stmt *Loop = BE->getDst()->getLoopTarget()) { 1141218887Sdim PathDiagnosticLocation L(Loop, PDB.getSourceManager()); 1142218887Sdim const CompoundStmt *CS = NULL; 1143218887Sdim 1144218887Sdim if (!Term) { 1145218887Sdim if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) 1146218887Sdim CS = dyn_cast<CompoundStmt>(FS->getBody()); 1147218887Sdim else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) 1148218887Sdim CS = dyn_cast<CompoundStmt>(WS->getBody()); 1149218887Sdim } 1150218887Sdim 1151218887Sdim PathDiagnosticEventPiece *p = 1152218887Sdim new PathDiagnosticEventPiece(L, 1153218887Sdim "Looping back to the head of the loop"); 1154218887Sdim 1155218887Sdim EB.addEdge(p->getLocation(), true); 1156218887Sdim PD.push_front(p); 1157218887Sdim 1158218887Sdim if (CS) { 1159218887Sdim PathDiagnosticLocation BL(CS->getRBracLoc(), 1160218887Sdim PDB.getSourceManager()); 1161218887Sdim BL = PathDiagnosticLocation(BL.asLocation()); 1162218887Sdim EB.addEdge(BL); 1163218887Sdim } 1164218887Sdim } 1165218887Sdim 1166218887Sdim if (Term) 1167218887Sdim EB.addContext(Term); 1168218887Sdim 1169218887Sdim break; 1170218887Sdim } 1171218887Sdim 1172218887Sdim if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) { 1173218887Sdim if (CFGStmt S = BE->getFirstElement().getAs<CFGStmt>()) { 1174218887Sdim if (IsControlFlowExpr(S)) { 1175218887Sdim // Add the proper context for '&&', '||', and '?'. 1176218887Sdim EB.addContext(S); 1177218887Sdim } 1178218887Sdim else 1179218887Sdim EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 1180218887Sdim } 1181218887Sdim 1182218887Sdim break; 1183218887Sdim } 1184218887Sdim } while (0); 1185218887Sdim 1186218887Sdim if (!NextNode) 1187218887Sdim continue; 1188218887Sdim 1189218887Sdim for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(), 1190218887Sdim E = PDB.visitor_end(); I!=E; ++I) { 1191218887Sdim if (PathDiagnosticPiece* p = (*I)->VisitNode(N, NextNode, PDB)) { 1192218887Sdim const PathDiagnosticLocation &Loc = p->getLocation(); 1193218887Sdim EB.addEdge(Loc, true); 1194218887Sdim PD.push_front(p); 1195218887Sdim if (const Stmt *S = Loc.asStmt()) 1196218887Sdim EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 1197218887Sdim } 1198218887Sdim } 1199218887Sdim } 1200218887Sdim} 1201218887Sdim 1202218887Sdim//===----------------------------------------------------------------------===// 1203218887Sdim// Methods for BugType and subclasses. 1204218887Sdim//===----------------------------------------------------------------------===// 1205219077SdimBugType::~BugType() { } 1206219077Sdim 1207218887Sdimvoid BugType::FlushReports(BugReporter &BR) {} 1208218887Sdim 1209218887Sdim//===----------------------------------------------------------------------===// 1210218887Sdim// Methods for BugReport and subclasses. 1211218887Sdim//===----------------------------------------------------------------------===// 1212218887SdimBugReport::~BugReport() {} 1213218887SdimRangedBugReport::~RangedBugReport() {} 1214218887Sdim 1215218887Sdimconst Stmt* BugReport::getStmt() const { 1216218887Sdim ProgramPoint ProgP = ErrorNode->getLocation(); 1217218887Sdim const Stmt *S = NULL; 1218218887Sdim 1219218887Sdim if (BlockEntrance* BE = dyn_cast<BlockEntrance>(&ProgP)) { 1220218887Sdim CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit(); 1221218887Sdim if (BE->getBlock() == &Exit) 1222218887Sdim S = GetPreviousStmt(ErrorNode); 1223218887Sdim } 1224218887Sdim if (!S) 1225218887Sdim S = GetStmt(ProgP); 1226218887Sdim 1227218887Sdim return S; 1228218887Sdim} 1229218887Sdim 1230218887SdimPathDiagnosticPiece* 1231218887SdimBugReport::getEndPath(BugReporterContext& BRC, 1232218887Sdim const ExplodedNode* EndPathNode) { 1233218887Sdim 1234218887Sdim const Stmt* S = getStmt(); 1235218887Sdim 1236218887Sdim if (!S) 1237218887Sdim return NULL; 1238218887Sdim 1239218887Sdim BugReport::ranges_iterator Beg, End; 1240218887Sdim llvm::tie(Beg, End) = getRanges(); 1241218887Sdim PathDiagnosticLocation L(S, BRC.getSourceManager()); 1242218887Sdim 1243218887Sdim // Only add the statement itself as a range if we didn't specify any 1244218887Sdim // special ranges for this report. 1245218887Sdim PathDiagnosticPiece* P = new PathDiagnosticEventPiece(L, getDescription(), 1246218887Sdim Beg == End); 1247218887Sdim 1248218887Sdim for (; Beg != End; ++Beg) 1249218887Sdim P->addRange(*Beg); 1250218887Sdim 1251218887Sdim return P; 1252218887Sdim} 1253218887Sdim 1254218887Sdimstd::pair<BugReport::ranges_iterator, BugReport::ranges_iterator> 1255218887SdimBugReport::getRanges() const { 1256218887Sdim if (const Expr* E = dyn_cast_or_null<Expr>(getStmt())) { 1257218887Sdim R = E->getSourceRange(); 1258218887Sdim assert(R.isValid()); 1259218887Sdim return std::make_pair(&R, &R+1); 1260218887Sdim } 1261218887Sdim else 1262218887Sdim return std::make_pair(ranges_iterator(), ranges_iterator()); 1263218887Sdim} 1264218887Sdim 1265218887SdimSourceLocation BugReport::getLocation() const { 1266218887Sdim if (ErrorNode) 1267218887Sdim if (const Stmt* S = GetCurrentOrPreviousStmt(ErrorNode)) { 1268218887Sdim // For member expressions, return the location of the '.' or '->'. 1269218887Sdim if (const MemberExpr *ME = dyn_cast<MemberExpr>(S)) 1270218887Sdim return ME->getMemberLoc(); 1271218887Sdim // For binary operators, return the location of the operator. 1272218887Sdim if (const BinaryOperator *B = dyn_cast<BinaryOperator>(S)) 1273218887Sdim return B->getOperatorLoc(); 1274218887Sdim 1275218887Sdim return S->getLocStart(); 1276218887Sdim } 1277218887Sdim 1278218887Sdim return FullSourceLoc(); 1279218887Sdim} 1280218887Sdim 1281218887SdimPathDiagnosticPiece* BugReport::VisitNode(const ExplodedNode* N, 1282218887Sdim const ExplodedNode* PrevN, 1283218887Sdim BugReporterContext &BRC) { 1284218887Sdim return NULL; 1285218887Sdim} 1286218887Sdim 1287218887Sdim//===----------------------------------------------------------------------===// 1288218887Sdim// Methods for BugReporter and subclasses. 1289218887Sdim//===----------------------------------------------------------------------===// 1290218887Sdim 1291218887SdimBugReportEquivClass::~BugReportEquivClass() { 1292218887Sdim for (iterator I=begin(), E=end(); I!=E; ++I) delete *I; 1293218887Sdim} 1294218887Sdim 1295218887SdimGRBugReporter::~GRBugReporter() { } 1296218887SdimBugReporterData::~BugReporterData() {} 1297218887Sdim 1298218887SdimExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); } 1299218887Sdim 1300218887SdimGRStateManager& 1301218887SdimGRBugReporter::getStateManager() { return Eng.getStateManager(); } 1302218887Sdim 1303218887SdimBugReporter::~BugReporter() { FlushReports(); } 1304218887Sdim 1305218887Sdimvoid BugReporter::FlushReports() { 1306218887Sdim if (BugTypes.isEmpty()) 1307218887Sdim return; 1308218887Sdim 1309218887Sdim // First flush the warnings for each BugType. This may end up creating new 1310219077Sdim // warnings and new BugTypes. 1311219077Sdim // FIXME: Only NSErrorChecker needs BugType's FlushReports. 1312219077Sdim // Turn NSErrorChecker into a proper checker and remove this. 1313219077Sdim llvm::SmallVector<const BugType*, 16> bugTypes; 1314218887Sdim for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I) 1315219077Sdim bugTypes.push_back(*I); 1316219077Sdim for (llvm::SmallVector<const BugType*, 16>::iterator 1317219077Sdim I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I) 1318218887Sdim const_cast<BugType*>(*I)->FlushReports(*this); 1319218887Sdim 1320219077Sdim typedef llvm::FoldingSet<BugReportEquivClass> SetTy; 1321219077Sdim for (SetTy::iterator EI=EQClasses.begin(), EE=EQClasses.end(); EI!=EE;++EI){ 1322219077Sdim BugReportEquivClass& EQ = *EI; 1323219077Sdim FlushReport(EQ); 1324219077Sdim } 1325218887Sdim 1326219077Sdim // BugReporter owns and deletes only BugTypes created implicitly through 1327219077Sdim // EmitBasicReport. 1328219077Sdim // FIXME: There are leaks from checkers that assume that the BugTypes they 1329219077Sdim // create will be destroyed by the BugReporter. 1330219077Sdim for (llvm::StringMap<BugType*>::iterator 1331219077Sdim I = StrBugTypes.begin(), E = StrBugTypes.end(); I != E; ++I) 1332219077Sdim delete I->second; 1333218887Sdim 1334218887Sdim // Remove all references to the BugType objects. 1335218887Sdim BugTypes = F.getEmptySet(); 1336218887Sdim} 1337218887Sdim 1338218887Sdim//===----------------------------------------------------------------------===// 1339218887Sdim// PathDiagnostics generation. 1340218887Sdim//===----------------------------------------------------------------------===// 1341218887Sdim 1342218887Sdimstatic std::pair<std::pair<ExplodedGraph*, NodeBackMap*>, 1343218887Sdim std::pair<ExplodedNode*, unsigned> > 1344218887SdimMakeReportGraph(const ExplodedGraph* G, 1345218887Sdim llvm::SmallVectorImpl<const ExplodedNode*> &nodes) { 1346218887Sdim 1347218887Sdim // Create the trimmed graph. It will contain the shortest paths from the 1348218887Sdim // error nodes to the root. In the new graph we should only have one 1349218887Sdim // error node unless there are two or more error nodes with the same minimum 1350218887Sdim // path length. 1351218887Sdim ExplodedGraph* GTrim; 1352218887Sdim InterExplodedGraphMap* NMap; 1353218887Sdim 1354218887Sdim llvm::DenseMap<const void*, const void*> InverseMap; 1355218887Sdim llvm::tie(GTrim, NMap) = G->Trim(nodes.data(), nodes.data() + nodes.size(), 1356218887Sdim &InverseMap); 1357218887Sdim 1358218887Sdim // Create owning pointers for GTrim and NMap just to ensure that they are 1359218887Sdim // released when this function exists. 1360218887Sdim llvm::OwningPtr<ExplodedGraph> AutoReleaseGTrim(GTrim); 1361218887Sdim llvm::OwningPtr<InterExplodedGraphMap> AutoReleaseNMap(NMap); 1362218887Sdim 1363218887Sdim // Find the (first) error node in the trimmed graph. We just need to consult 1364218887Sdim // the node map (NMap) which maps from nodes in the original graph to nodes 1365218887Sdim // in the new graph. 1366218887Sdim 1367218887Sdim std::queue<const ExplodedNode*> WS; 1368218887Sdim typedef llvm::DenseMap<const ExplodedNode*, unsigned> IndexMapTy; 1369218887Sdim IndexMapTy IndexMap; 1370218887Sdim 1371218887Sdim for (unsigned nodeIndex = 0 ; nodeIndex < nodes.size(); ++nodeIndex) { 1372218887Sdim const ExplodedNode *originalNode = nodes[nodeIndex]; 1373218887Sdim if (const ExplodedNode *N = NMap->getMappedNode(originalNode)) { 1374218887Sdim WS.push(N); 1375218887Sdim IndexMap[originalNode] = nodeIndex; 1376218887Sdim } 1377218887Sdim } 1378218887Sdim 1379218887Sdim assert(!WS.empty() && "No error node found in the trimmed graph."); 1380218887Sdim 1381218887Sdim // Create a new (third!) graph with a single path. This is the graph 1382218887Sdim // that will be returned to the caller. 1383218887Sdim ExplodedGraph *GNew = new ExplodedGraph(); 1384218887Sdim 1385218887Sdim // Sometimes the trimmed graph can contain a cycle. Perform a reverse BFS 1386218887Sdim // to the root node, and then construct a new graph that contains only 1387218887Sdim // a single path. 1388218887Sdim llvm::DenseMap<const void*,unsigned> Visited; 1389218887Sdim 1390218887Sdim unsigned cnt = 0; 1391218887Sdim const ExplodedNode* Root = 0; 1392218887Sdim 1393218887Sdim while (!WS.empty()) { 1394218887Sdim const ExplodedNode* Node = WS.front(); 1395218887Sdim WS.pop(); 1396218887Sdim 1397218887Sdim if (Visited.find(Node) != Visited.end()) 1398218887Sdim continue; 1399218887Sdim 1400218887Sdim Visited[Node] = cnt++; 1401218887Sdim 1402218887Sdim if (Node->pred_empty()) { 1403218887Sdim Root = Node; 1404218887Sdim break; 1405218887Sdim } 1406218887Sdim 1407218887Sdim for (ExplodedNode::const_pred_iterator I=Node->pred_begin(), 1408218887Sdim E=Node->pred_end(); I!=E; ++I) 1409218887Sdim WS.push(*I); 1410218887Sdim } 1411218887Sdim 1412218887Sdim assert(Root); 1413218887Sdim 1414218887Sdim // Now walk from the root down the BFS path, always taking the successor 1415218887Sdim // with the lowest number. 1416218887Sdim ExplodedNode *Last = 0, *First = 0; 1417218887Sdim NodeBackMap *BM = new NodeBackMap(); 1418218887Sdim unsigned NodeIndex = 0; 1419218887Sdim 1420218887Sdim for ( const ExplodedNode *N = Root ;;) { 1421218887Sdim // Lookup the number associated with the current node. 1422218887Sdim llvm::DenseMap<const void*,unsigned>::iterator I = Visited.find(N); 1423218887Sdim assert(I != Visited.end()); 1424218887Sdim 1425218887Sdim // Create the equivalent node in the new graph with the same state 1426218887Sdim // and location. 1427218887Sdim ExplodedNode* NewN = GNew->getNode(N->getLocation(), N->getState()); 1428218887Sdim 1429218887Sdim // Store the mapping to the original node. 1430218887Sdim llvm::DenseMap<const void*, const void*>::iterator IMitr=InverseMap.find(N); 1431218887Sdim assert(IMitr != InverseMap.end() && "No mapping to original node."); 1432218887Sdim (*BM)[NewN] = (const ExplodedNode*) IMitr->second; 1433218887Sdim 1434218887Sdim // Link up the new node with the previous node. 1435218887Sdim if (Last) 1436218887Sdim NewN->addPredecessor(Last, *GNew); 1437218887Sdim 1438218887Sdim Last = NewN; 1439218887Sdim 1440218887Sdim // Are we at the final node? 1441218887Sdim IndexMapTy::iterator IMI = 1442218887Sdim IndexMap.find((const ExplodedNode*)(IMitr->second)); 1443218887Sdim if (IMI != IndexMap.end()) { 1444218887Sdim First = NewN; 1445218887Sdim NodeIndex = IMI->second; 1446218887Sdim break; 1447218887Sdim } 1448218887Sdim 1449218887Sdim // Find the next successor node. We choose the node that is marked 1450218887Sdim // with the lowest DFS number. 1451218887Sdim ExplodedNode::const_succ_iterator SI = N->succ_begin(); 1452218887Sdim ExplodedNode::const_succ_iterator SE = N->succ_end(); 1453218887Sdim N = 0; 1454218887Sdim 1455218887Sdim for (unsigned MinVal = 0; SI != SE; ++SI) { 1456218887Sdim 1457218887Sdim I = Visited.find(*SI); 1458218887Sdim 1459218887Sdim if (I == Visited.end()) 1460218887Sdim continue; 1461218887Sdim 1462218887Sdim if (!N || I->second < MinVal) { 1463218887Sdim N = *SI; 1464218887Sdim MinVal = I->second; 1465218887Sdim } 1466218887Sdim } 1467218887Sdim 1468218887Sdim assert(N); 1469218887Sdim } 1470218887Sdim 1471218887Sdim assert(First); 1472218887Sdim 1473218887Sdim return std::make_pair(std::make_pair(GNew, BM), 1474218887Sdim std::make_pair(First, NodeIndex)); 1475218887Sdim} 1476218887Sdim 1477218887Sdim/// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object 1478218887Sdim/// and collapses PathDiagosticPieces that are expanded by macros. 1479218887Sdimstatic void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM) { 1480218887Sdim typedef std::vector<std::pair<PathDiagnosticMacroPiece*, SourceLocation> > 1481218887Sdim MacroStackTy; 1482218887Sdim 1483218887Sdim typedef std::vector<PathDiagnosticPiece*> 1484218887Sdim PiecesTy; 1485218887Sdim 1486218887Sdim MacroStackTy MacroStack; 1487218887Sdim PiecesTy Pieces; 1488218887Sdim 1489218887Sdim for (PathDiagnostic::iterator I = PD.begin(), E = PD.end(); I!=E; ++I) { 1490218887Sdim // Get the location of the PathDiagnosticPiece. 1491218887Sdim const FullSourceLoc Loc = I->getLocation().asLocation(); 1492218887Sdim 1493218887Sdim // Determine the instantiation location, which is the location we group 1494218887Sdim // related PathDiagnosticPieces. 1495218887Sdim SourceLocation InstantiationLoc = Loc.isMacroID() ? 1496218887Sdim SM.getInstantiationLoc(Loc) : 1497218887Sdim SourceLocation(); 1498218887Sdim 1499218887Sdim if (Loc.isFileID()) { 1500218887Sdim MacroStack.clear(); 1501218887Sdim Pieces.push_back(&*I); 1502218887Sdim continue; 1503218887Sdim } 1504218887Sdim 1505218887Sdim assert(Loc.isMacroID()); 1506218887Sdim 1507218887Sdim // Is the PathDiagnosticPiece within the same macro group? 1508218887Sdim if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) { 1509218887Sdim MacroStack.back().first->push_back(&*I); 1510218887Sdim continue; 1511218887Sdim } 1512218887Sdim 1513218887Sdim // We aren't in the same group. Are we descending into a new macro 1514218887Sdim // or are part of an old one? 1515218887Sdim PathDiagnosticMacroPiece *MacroGroup = 0; 1516218887Sdim 1517218887Sdim SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ? 1518218887Sdim SM.getInstantiationLoc(Loc) : 1519218887Sdim SourceLocation(); 1520218887Sdim 1521218887Sdim // Walk the entire macro stack. 1522218887Sdim while (!MacroStack.empty()) { 1523218887Sdim if (InstantiationLoc == MacroStack.back().second) { 1524218887Sdim MacroGroup = MacroStack.back().first; 1525218887Sdim break; 1526218887Sdim } 1527218887Sdim 1528218887Sdim if (ParentInstantiationLoc == MacroStack.back().second) { 1529218887Sdim MacroGroup = MacroStack.back().first; 1530218887Sdim break; 1531218887Sdim } 1532218887Sdim 1533218887Sdim MacroStack.pop_back(); 1534218887Sdim } 1535218887Sdim 1536218887Sdim if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) { 1537218887Sdim // Create a new macro group and add it to the stack. 1538218887Sdim PathDiagnosticMacroPiece *NewGroup = new PathDiagnosticMacroPiece(Loc); 1539218887Sdim 1540218887Sdim if (MacroGroup) 1541218887Sdim MacroGroup->push_back(NewGroup); 1542218887Sdim else { 1543218887Sdim assert(InstantiationLoc.isFileID()); 1544218887Sdim Pieces.push_back(NewGroup); 1545218887Sdim } 1546218887Sdim 1547218887Sdim MacroGroup = NewGroup; 1548218887Sdim MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc)); 1549218887Sdim } 1550218887Sdim 1551218887Sdim // Finally, add the PathDiagnosticPiece to the group. 1552218887Sdim MacroGroup->push_back(&*I); 1553218887Sdim } 1554218887Sdim 1555218887Sdim // Now take the pieces and construct a new PathDiagnostic. 1556218887Sdim PD.resetPath(false); 1557218887Sdim 1558218887Sdim for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I) { 1559218887Sdim if (PathDiagnosticMacroPiece *MP=dyn_cast<PathDiagnosticMacroPiece>(*I)) 1560218887Sdim if (!MP->containsEvent()) { 1561218887Sdim delete MP; 1562218887Sdim continue; 1563218887Sdim } 1564218887Sdim 1565218887Sdim PD.push_back(*I); 1566218887Sdim } 1567218887Sdim} 1568218887Sdim 1569218887Sdimvoid GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, 1570218887Sdim llvm::SmallVectorImpl<BugReport *> &bugReports) { 1571218887Sdim 1572218887Sdim assert(!bugReports.empty()); 1573218887Sdim llvm::SmallVector<const ExplodedNode *, 10> errorNodes; 1574218887Sdim for (llvm::SmallVectorImpl<BugReport*>::iterator I = bugReports.begin(), 1575218887Sdim E = bugReports.end(); I != E; ++I) { 1576218887Sdim errorNodes.push_back((*I)->getErrorNode()); 1577218887Sdim } 1578218887Sdim 1579218887Sdim // Construct a new graph that contains only a single path from the error 1580218887Sdim // node to a root. 1581218887Sdim const std::pair<std::pair<ExplodedGraph*, NodeBackMap*>, 1582218887Sdim std::pair<ExplodedNode*, unsigned> >& 1583218887Sdim GPair = MakeReportGraph(&getGraph(), errorNodes); 1584218887Sdim 1585218887Sdim // Find the BugReport with the original location. 1586218887Sdim assert(GPair.second.second < bugReports.size()); 1587218887Sdim BugReport *R = bugReports[GPair.second.second]; 1588218887Sdim assert(R && "No original report found for sliced graph."); 1589218887Sdim 1590218887Sdim llvm::OwningPtr<ExplodedGraph> ReportGraph(GPair.first.first); 1591218887Sdim llvm::OwningPtr<NodeBackMap> BackMap(GPair.first.second); 1592218887Sdim const ExplodedNode *N = GPair.second.first; 1593218887Sdim 1594218887Sdim // Start building the path diagnostic... 1595218887Sdim PathDiagnosticBuilder PDB(*this, R, BackMap.get(), getPathDiagnosticClient()); 1596218887Sdim 1597218887Sdim if (PathDiagnosticPiece* Piece = R->getEndPath(PDB, N)) 1598218887Sdim PD.push_back(Piece); 1599218887Sdim else 1600218887Sdim return; 1601218887Sdim 1602218887Sdim // Register node visitors. 1603218887Sdim R->registerInitialVisitors(PDB, N); 1604218887Sdim bugreporter::registerNilReceiverVisitor(PDB); 1605218887Sdim 1606218887Sdim switch (PDB.getGenerationScheme()) { 1607218887Sdim case PathDiagnosticClient::Extensive: 1608218887Sdim GenerateExtensivePathDiagnostic(PD, PDB, N); 1609218887Sdim break; 1610218887Sdim case PathDiagnosticClient::Minimal: 1611218887Sdim GenerateMinimalPathDiagnostic(PD, PDB, N); 1612218887Sdim break; 1613218887Sdim } 1614218887Sdim} 1615218887Sdim 1616218887Sdimvoid BugReporter::Register(BugType *BT) { 1617218887Sdim BugTypes = F.add(BugTypes, BT); 1618218887Sdim} 1619218887Sdim 1620218887Sdimvoid BugReporter::EmitReport(BugReport* R) { 1621218887Sdim // Compute the bug report's hash to determine its equivalence class. 1622218887Sdim llvm::FoldingSetNodeID ID; 1623218887Sdim R->Profile(ID); 1624218887Sdim 1625218887Sdim // Lookup the equivance class. If there isn't one, create it. 1626218887Sdim BugType& BT = R->getBugType(); 1627218887Sdim Register(&BT); 1628218887Sdim void *InsertPos; 1629219077Sdim BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos); 1630218887Sdim 1631218887Sdim if (!EQ) { 1632218887Sdim EQ = new BugReportEquivClass(R); 1633219077Sdim EQClasses.InsertNode(EQ, InsertPos); 1634218887Sdim } 1635218887Sdim else 1636218887Sdim EQ->AddReport(R); 1637218887Sdim} 1638218887Sdim 1639218887Sdim 1640218887Sdim//===----------------------------------------------------------------------===// 1641218887Sdim// Emitting reports in equivalence classes. 1642218887Sdim//===----------------------------------------------------------------------===// 1643218887Sdim 1644218887Sdimnamespace { 1645218887Sdimstruct FRIEC_WLItem { 1646218887Sdim const ExplodedNode *N; 1647218887Sdim ExplodedNode::const_succ_iterator I, E; 1648218887Sdim 1649218887Sdim FRIEC_WLItem(const ExplodedNode *n) 1650218887Sdim : N(n), I(N->succ_begin()), E(N->succ_end()) {} 1651218887Sdim}; 1652218887Sdim} 1653218887Sdim 1654218887Sdimstatic BugReport * 1655218887SdimFindReportInEquivalenceClass(BugReportEquivClass& EQ, 1656218887Sdim llvm::SmallVectorImpl<BugReport*> &bugReports) { 1657218887Sdim 1658218887Sdim BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end(); 1659218887Sdim assert(I != E); 1660218887Sdim BugReport *R = *I; 1661218887Sdim BugType& BT = R->getBugType(); 1662218887Sdim 1663218887Sdim // If we don't need to suppress any of the nodes because they are 1664218887Sdim // post-dominated by a sink, simply add all the nodes in the equivalence class 1665218887Sdim // to 'Nodes'. Any of the reports will serve as a "representative" report. 1666218887Sdim if (!BT.isSuppressOnSink()) { 1667218887Sdim for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) { 1668218887Sdim const ExplodedNode* N = I->getErrorNode(); 1669218887Sdim if (N) { 1670218887Sdim R = *I; 1671218887Sdim bugReports.push_back(R); 1672218887Sdim } 1673218887Sdim } 1674218887Sdim return R; 1675218887Sdim } 1676218887Sdim 1677218887Sdim // For bug reports that should be suppressed when all paths are post-dominated 1678218887Sdim // by a sink node, iterate through the reports in the equivalence class 1679218887Sdim // until we find one that isn't post-dominated (if one exists). We use a 1680218887Sdim // DFS traversal of the ExplodedGraph to find a non-sink node. We could write 1681218887Sdim // this as a recursive function, but we don't want to risk blowing out the 1682218887Sdim // stack for very long paths. 1683218887Sdim BugReport *exampleReport = 0; 1684218887Sdim 1685218887Sdim for (; I != E; ++I) { 1686218887Sdim R = *I; 1687218887Sdim const ExplodedNode *errorNode = R->getErrorNode(); 1688218887Sdim 1689218887Sdim if (!errorNode) 1690218887Sdim continue; 1691218887Sdim if (errorNode->isSink()) { 1692218887Sdim assert(false && 1693218887Sdim "BugType::isSuppressSink() should not be 'true' for sink end nodes"); 1694218887Sdim return 0; 1695218887Sdim } 1696218887Sdim // No successors? By definition this nodes isn't post-dominated by a sink. 1697218887Sdim if (errorNode->succ_empty()) { 1698218887Sdim bugReports.push_back(R); 1699218887Sdim if (!exampleReport) 1700218887Sdim exampleReport = R; 1701218887Sdim continue; 1702218887Sdim } 1703218887Sdim 1704218887Sdim // At this point we know that 'N' is not a sink and it has at least one 1705218887Sdim // successor. Use a DFS worklist to find a non-sink end-of-path node. 1706218887Sdim typedef FRIEC_WLItem WLItem; 1707218887Sdim typedef llvm::SmallVector<WLItem, 10> DFSWorkList; 1708218887Sdim llvm::DenseMap<const ExplodedNode *, unsigned> Visited; 1709218887Sdim 1710218887Sdim DFSWorkList WL; 1711218887Sdim WL.push_back(errorNode); 1712218887Sdim Visited[errorNode] = 1; 1713218887Sdim 1714218887Sdim while (!WL.empty()) { 1715218887Sdim WLItem &WI = WL.back(); 1716218887Sdim assert(!WI.N->succ_empty()); 1717218887Sdim 1718218887Sdim for (; WI.I != WI.E; ++WI.I) { 1719218887Sdim const ExplodedNode *Succ = *WI.I; 1720218887Sdim // End-of-path node? 1721218887Sdim if (Succ->succ_empty()) { 1722218887Sdim // If we found an end-of-path node that is not a sink. 1723218887Sdim if (!Succ->isSink()) { 1724218887Sdim bugReports.push_back(R); 1725218887Sdim if (!exampleReport) 1726218887Sdim exampleReport = R; 1727218887Sdim WL.clear(); 1728218887Sdim break; 1729218887Sdim } 1730218887Sdim // Found a sink? Continue on to the next successor. 1731218887Sdim continue; 1732218887Sdim } 1733218887Sdim // Mark the successor as visited. If it hasn't been explored, 1734218887Sdim // enqueue it to the DFS worklist. 1735218887Sdim unsigned &mark = Visited[Succ]; 1736218887Sdim if (!mark) { 1737218887Sdim mark = 1; 1738218887Sdim WL.push_back(Succ); 1739218887Sdim break; 1740218887Sdim } 1741218887Sdim } 1742218887Sdim 1743218887Sdim // The worklist may have been cleared at this point. First 1744218887Sdim // check if it is empty before checking the last item. 1745218887Sdim if (!WL.empty() && &WL.back() == &WI) 1746218887Sdim WL.pop_back(); 1747218887Sdim } 1748218887Sdim } 1749218887Sdim 1750218887Sdim // ExampleReport will be NULL if all the nodes in the equivalence class 1751218887Sdim // were post-dominated by sinks. 1752218887Sdim return exampleReport; 1753218887Sdim} 1754218887Sdim 1755218887Sdim//===----------------------------------------------------------------------===// 1756218887Sdim// DiagnosticCache. This is a hack to cache analyzer diagnostics. It 1757218887Sdim// uses global state, which eventually should go elsewhere. 1758218887Sdim//===----------------------------------------------------------------------===// 1759218887Sdimnamespace { 1760218887Sdimclass DiagCacheItem : public llvm::FoldingSetNode { 1761218887Sdim llvm::FoldingSetNodeID ID; 1762218887Sdimpublic: 1763218887Sdim DiagCacheItem(BugReport *R, PathDiagnostic *PD) { 1764218887Sdim ID.AddString(R->getBugType().getName()); 1765218887Sdim ID.AddString(R->getBugType().getCategory()); 1766218887Sdim ID.AddString(R->getDescription()); 1767218887Sdim ID.AddInteger(R->getLocation().getRawEncoding()); 1768218887Sdim PD->Profile(ID); 1769218887Sdim } 1770218887Sdim 1771218887Sdim void Profile(llvm::FoldingSetNodeID &id) { 1772218887Sdim id = ID; 1773218887Sdim } 1774218887Sdim 1775218887Sdim llvm::FoldingSetNodeID &getID() { return ID; } 1776218887Sdim}; 1777218887Sdim} 1778218887Sdim 1779218887Sdimstatic bool IsCachedDiagnostic(BugReport *R, PathDiagnostic *PD) { 1780218887Sdim // FIXME: Eventually this diagnostic cache should reside in something 1781218887Sdim // like AnalysisManager instead of being a static variable. This is 1782218887Sdim // really unsafe in the long term. 1783218887Sdim typedef llvm::FoldingSet<DiagCacheItem> DiagnosticCache; 1784218887Sdim static DiagnosticCache DC; 1785218887Sdim 1786218887Sdim void *InsertPos; 1787218887Sdim DiagCacheItem *Item = new DiagCacheItem(R, PD); 1788218887Sdim 1789218887Sdim if (DC.FindNodeOrInsertPos(Item->getID(), InsertPos)) { 1790218887Sdim delete Item; 1791218887Sdim return true; 1792218887Sdim } 1793218887Sdim 1794218887Sdim DC.InsertNode(Item, InsertPos); 1795218887Sdim return false; 1796218887Sdim} 1797218887Sdim 1798218887Sdimvoid BugReporter::FlushReport(BugReportEquivClass& EQ) { 1799218887Sdim llvm::SmallVector<BugReport*, 10> bugReports; 1800218887Sdim BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports); 1801218887Sdim if (!exampleReport) 1802218887Sdim return; 1803218887Sdim 1804218887Sdim PathDiagnosticClient* PD = getPathDiagnosticClient(); 1805218887Sdim 1806218887Sdim // FIXME: Make sure we use the 'R' for the path that was actually used. 1807218887Sdim // Probably doesn't make a difference in practice. 1808218887Sdim BugType& BT = exampleReport->getBugType(); 1809218887Sdim 1810218887Sdim llvm::OwningPtr<PathDiagnostic> 1811218887Sdim D(new PathDiagnostic(exampleReport->getBugType().getName(), 1812218887Sdim !PD || PD->useVerboseDescription() 1813218887Sdim ? exampleReport->getDescription() 1814218887Sdim : exampleReport->getShortDescription(), 1815218887Sdim BT.getCategory())); 1816218887Sdim 1817218887Sdim if (!bugReports.empty()) 1818218887Sdim GeneratePathDiagnostic(*D.get(), bugReports); 1819218887Sdim 1820218887Sdim if (IsCachedDiagnostic(exampleReport, D.get())) 1821218887Sdim return; 1822218887Sdim 1823218887Sdim // Get the meta data. 1824218887Sdim std::pair<const char**, const char**> Meta = 1825218887Sdim exampleReport->getExtraDescriptiveText(); 1826218887Sdim for (const char** s = Meta.first; s != Meta.second; ++s) 1827218887Sdim D->addMeta(*s); 1828218887Sdim 1829218887Sdim // Emit a summary diagnostic to the regular Diagnostics engine. 1830218887Sdim BugReport::ranges_iterator Beg, End; 1831218887Sdim llvm::tie(Beg, End) = exampleReport->getRanges(); 1832218887Sdim Diagnostic &Diag = getDiagnostic(); 1833218887Sdim FullSourceLoc L(exampleReport->getLocation(), getSourceManager()); 1834218887Sdim 1835218887Sdim // Search the description for '%', as that will be interpretted as a 1836218887Sdim // format character by FormatDiagnostics. 1837218887Sdim llvm::StringRef desc = exampleReport->getShortDescription(); 1838218887Sdim unsigned ErrorDiag; 1839218887Sdim { 1840218887Sdim llvm::SmallString<512> TmpStr; 1841218887Sdim llvm::raw_svector_ostream Out(TmpStr); 1842218887Sdim for (llvm::StringRef::iterator I=desc.begin(), E=desc.end(); I!=E; ++I) 1843218887Sdim if (*I == '%') 1844218887Sdim Out << "%%"; 1845218887Sdim else 1846218887Sdim Out << *I; 1847218887Sdim 1848218887Sdim Out.flush(); 1849218887Sdim ErrorDiag = Diag.getCustomDiagID(Diagnostic::Warning, TmpStr); 1850218887Sdim } 1851218887Sdim 1852218887Sdim { 1853218887Sdim DiagnosticBuilder diagBuilder = Diag.Report(L, ErrorDiag); 1854218887Sdim for (BugReport::ranges_iterator I = Beg; I != End; ++I) 1855218887Sdim diagBuilder << *I; 1856218887Sdim } 1857218887Sdim 1858218887Sdim // Emit a full diagnostic for the path if we have a PathDiagnosticClient. 1859218887Sdim if (!PD) 1860218887Sdim return; 1861218887Sdim 1862218887Sdim if (D->empty()) { 1863218887Sdim PathDiagnosticPiece* piece = 1864218887Sdim new PathDiagnosticEventPiece(L, exampleReport->getDescription()); 1865218887Sdim 1866218887Sdim for ( ; Beg != End; ++Beg) piece->addRange(*Beg); 1867218887Sdim D->push_back(piece); 1868218887Sdim } 1869218887Sdim 1870218887Sdim PD->HandlePathDiagnostic(D.take()); 1871218887Sdim} 1872218887Sdim 1873218887Sdimvoid BugReporter::EmitBasicReport(llvm::StringRef name, llvm::StringRef str, 1874218887Sdim SourceLocation Loc, 1875218887Sdim SourceRange* RBeg, unsigned NumRanges) { 1876218887Sdim EmitBasicReport(name, "", str, Loc, RBeg, NumRanges); 1877218887Sdim} 1878218887Sdim 1879218887Sdimvoid BugReporter::EmitBasicReport(llvm::StringRef name, 1880218887Sdim llvm::StringRef category, 1881218887Sdim llvm::StringRef str, SourceLocation Loc, 1882218887Sdim SourceRange* RBeg, unsigned NumRanges) { 1883218887Sdim 1884219077Sdim // 'BT' is owned by BugReporter. 1885219077Sdim BugType *BT = getBugTypeForName(name, category); 1886218887Sdim FullSourceLoc L = getContext().getFullLoc(Loc); 1887218887Sdim RangedBugReport *R = new DiagBugReport(*BT, str, L); 1888218887Sdim for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg); 1889218887Sdim EmitReport(R); 1890218887Sdim} 1891219077Sdim 1892219077SdimBugType *BugReporter::getBugTypeForName(llvm::StringRef name, 1893219077Sdim llvm::StringRef category) { 1894219077Sdim llvm::SmallString<136> fullDesc; 1895219077Sdim llvm::raw_svector_ostream(fullDesc) << name << ":" << category; 1896219077Sdim llvm::StringMapEntry<BugType *> & 1897219077Sdim entry = StrBugTypes.GetOrCreateValue(fullDesc); 1898219077Sdim BugType *BT = entry.getValue(); 1899219077Sdim if (!BT) { 1900219077Sdim BT = new BugType(name, category); 1901219077Sdim entry.setValue(BT); 1902219077Sdim } 1903219077Sdim return BT; 1904219077Sdim} 1905