BugReporter.cpp revision 239462
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" 20234353Sdim#include "clang/AST/DeclObjC.h" 21218887Sdim#include "clang/AST/Expr.h" 22218887Sdim#include "clang/AST/ParentMap.h" 23218887Sdim#include "clang/AST/StmtObjC.h" 24218887Sdim#include "clang/Basic/SourceManager.h" 25218887Sdim#include "clang/Analysis/ProgramPoint.h" 26218887Sdim#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" 27218887Sdim#include "llvm/Support/raw_ostream.h" 28218887Sdim#include "llvm/ADT/DenseMap.h" 29234353Sdim#include "llvm/ADT/SmallString.h" 30218887Sdim#include "llvm/ADT/STLExtras.h" 31218887Sdim#include "llvm/ADT/OwningPtr.h" 32234353Sdim#include "llvm/ADT/IntrusiveRefCntPtr.h" 33218887Sdim#include <queue> 34218887Sdim 35218887Sdimusing namespace clang; 36218887Sdimusing namespace ento; 37218887Sdim 38218887SdimBugReporterVisitor::~BugReporterVisitor() {} 39218887Sdim 40234353Sdimvoid BugReporterContext::anchor() {} 41234353Sdim 42218887Sdim//===----------------------------------------------------------------------===// 43218887Sdim// Helper routines for walking the ExplodedGraph and fetching statements. 44218887Sdim//===----------------------------------------------------------------------===// 45218887Sdim 46226633Sdimstatic inline const Stmt *GetStmt(const ProgramPoint &P) { 47218887Sdim if (const StmtPoint* SP = dyn_cast<StmtPoint>(&P)) 48218887Sdim return SP->getStmt(); 49226633Sdim else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) 50218887Sdim return BE->getSrc()->getTerminator(); 51239462Sdim else if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) 52239462Sdim return CE->getCallExpr(); 53239462Sdim else if (const CallExitEnd *CEE = dyn_cast<CallExitEnd>(&P)) 54239462Sdim return CEE->getCalleeContext()->getCallSite(); 55218887Sdim 56218887Sdim return 0; 57218887Sdim} 58218887Sdim 59218887Sdimstatic inline const ExplodedNode* 60226633SdimGetPredecessorNode(const ExplodedNode *N) { 61218887Sdim return N->pred_empty() ? NULL : *(N->pred_begin()); 62218887Sdim} 63218887Sdim 64218887Sdimstatic inline const ExplodedNode* 65226633SdimGetSuccessorNode(const ExplodedNode *N) { 66218887Sdim return N->succ_empty() ? NULL : *(N->succ_begin()); 67218887Sdim} 68218887Sdim 69226633Sdimstatic const Stmt *GetPreviousStmt(const ExplodedNode *N) { 70218887Sdim for (N = GetPredecessorNode(N); N; N = GetPredecessorNode(N)) 71218887Sdim if (const Stmt *S = GetStmt(N->getLocation())) 72218887Sdim return S; 73218887Sdim 74218887Sdim return 0; 75218887Sdim} 76218887Sdim 77226633Sdimstatic const Stmt *GetNextStmt(const ExplodedNode *N) { 78218887Sdim for (N = GetSuccessorNode(N); N; N = GetSuccessorNode(N)) 79218887Sdim if (const Stmt *S = GetStmt(N->getLocation())) { 80218887Sdim // Check if the statement is '?' or '&&'/'||'. These are "merges", 81218887Sdim // not actual statement points. 82218887Sdim switch (S->getStmtClass()) { 83218887Sdim case Stmt::ChooseExprClass: 84218887Sdim case Stmt::BinaryConditionalOperatorClass: continue; 85218887Sdim case Stmt::ConditionalOperatorClass: continue; 86218887Sdim case Stmt::BinaryOperatorClass: { 87218887Sdim BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode(); 88218887Sdim if (Op == BO_LAnd || Op == BO_LOr) 89218887Sdim continue; 90218887Sdim break; 91218887Sdim } 92218887Sdim default: 93218887Sdim break; 94218887Sdim } 95218887Sdim return S; 96218887Sdim } 97218887Sdim 98218887Sdim return 0; 99218887Sdim} 100218887Sdim 101218887Sdimstatic inline const Stmt* 102226633SdimGetCurrentOrPreviousStmt(const ExplodedNode *N) { 103218887Sdim if (const Stmt *S = GetStmt(N->getLocation())) 104218887Sdim return S; 105218887Sdim 106218887Sdim return GetPreviousStmt(N); 107218887Sdim} 108218887Sdim 109218887Sdimstatic inline const Stmt* 110226633SdimGetCurrentOrNextStmt(const ExplodedNode *N) { 111218887Sdim if (const Stmt *S = GetStmt(N->getLocation())) 112218887Sdim return S; 113218887Sdim 114218887Sdim return GetNextStmt(N); 115218887Sdim} 116218887Sdim 117218887Sdim//===----------------------------------------------------------------------===// 118234353Sdim// Diagnostic cleanup. 119234353Sdim//===----------------------------------------------------------------------===// 120234353Sdim 121234353Sdim/// Recursively scan through a path and prune out calls and macros pieces 122234353Sdim/// that aren't needed. Return true if afterwards the path contains 123234353Sdim/// "interesting stuff" which means it should be pruned from the parent path. 124234353Sdimstatic bool RemoveUneededCalls(PathPieces &pieces) { 125234353Sdim bool containsSomethingInteresting = false; 126234353Sdim const unsigned N = pieces.size(); 127234353Sdim 128234353Sdim for (unsigned i = 0 ; i < N ; ++i) { 129234353Sdim // Remove the front piece from the path. If it is still something we 130234353Sdim // want to keep once we are done, we will push it back on the end. 131234353Sdim IntrusiveRefCntPtr<PathDiagnosticPiece> piece(pieces.front()); 132234353Sdim pieces.pop_front(); 133234353Sdim 134234353Sdim switch (piece->getKind()) { 135234353Sdim case PathDiagnosticPiece::Call: { 136234353Sdim PathDiagnosticCallPiece *call = cast<PathDiagnosticCallPiece>(piece); 137234353Sdim // Recursively clean out the subclass. Keep this call around if 138234353Sdim // it contains any informative diagnostics. 139234353Sdim if (!RemoveUneededCalls(call->path)) 140234353Sdim continue; 141234353Sdim containsSomethingInteresting = true; 142234353Sdim break; 143234353Sdim } 144234353Sdim case PathDiagnosticPiece::Macro: { 145234353Sdim PathDiagnosticMacroPiece *macro = cast<PathDiagnosticMacroPiece>(piece); 146234353Sdim if (!RemoveUneededCalls(macro->subPieces)) 147234353Sdim continue; 148234353Sdim containsSomethingInteresting = true; 149234353Sdim break; 150234353Sdim } 151234353Sdim case PathDiagnosticPiece::Event: { 152234353Sdim PathDiagnosticEventPiece *event = cast<PathDiagnosticEventPiece>(piece); 153234353Sdim // We never throw away an event, but we do throw it away wholesale 154234353Sdim // as part of a path if we throw the entire path away. 155234353Sdim if (event->isPrunable()) 156234353Sdim continue; 157234353Sdim containsSomethingInteresting = true; 158234353Sdim break; 159234353Sdim } 160234353Sdim case PathDiagnosticPiece::ControlFlow: 161234353Sdim break; 162234353Sdim } 163234353Sdim 164234353Sdim pieces.push_back(piece); 165234353Sdim } 166234353Sdim 167234353Sdim return containsSomethingInteresting; 168234353Sdim} 169234353Sdim 170234353Sdim//===----------------------------------------------------------------------===// 171218887Sdim// PathDiagnosticBuilder and its associated routines and helper objects. 172218887Sdim//===----------------------------------------------------------------------===// 173218887Sdim 174218887Sdimtypedef llvm::DenseMap<const ExplodedNode*, 175218887Sdimconst ExplodedNode*> NodeBackMap; 176218887Sdim 177218887Sdimnamespace { 178218887Sdimclass NodeMapClosure : public BugReport::NodeResolver { 179218887Sdim NodeBackMap& M; 180218887Sdimpublic: 181218887Sdim NodeMapClosure(NodeBackMap *m) : M(*m) {} 182218887Sdim ~NodeMapClosure() {} 183218887Sdim 184226633Sdim const ExplodedNode *getOriginalNode(const ExplodedNode *N) { 185218887Sdim NodeBackMap::iterator I = M.find(N); 186218887Sdim return I == M.end() ? 0 : I->second; 187218887Sdim } 188218887Sdim}; 189218887Sdim 190218887Sdimclass PathDiagnosticBuilder : public BugReporterContext { 191218887Sdim BugReport *R; 192226633Sdim PathDiagnosticConsumer *PDC; 193234353Sdim OwningPtr<ParentMap> PM; 194218887Sdim NodeMapClosure NMC; 195218887Sdimpublic: 196234353Sdim const LocationContext *LC; 197234353Sdim 198218887Sdim PathDiagnosticBuilder(GRBugReporter &br, 199218887Sdim BugReport *r, NodeBackMap *Backmap, 200226633Sdim PathDiagnosticConsumer *pdc) 201218887Sdim : BugReporterContext(br), 202234353Sdim R(r), PDC(pdc), NMC(Backmap), LC(r->getErrorNode()->getLocationContext()) 203234353Sdim {} 204218887Sdim 205226633Sdim PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N); 206218887Sdim 207226633Sdim PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os, 208226633Sdim const ExplodedNode *N); 209218887Sdim 210226633Sdim BugReport *getBugReport() { return R; } 211226633Sdim 212218887Sdim Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); } 213234353Sdim 214234353Sdim ParentMap& getParentMap() { return LC->getParentMap(); } 215218887Sdim 216218887Sdim const Stmt *getParent(const Stmt *S) { 217218887Sdim return getParentMap().getParent(S); 218218887Sdim } 219218887Sdim 220218887Sdim virtual NodeMapClosure& getNodeResolver() { return NMC; } 221218887Sdim 222218887Sdim PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S); 223218887Sdim 224226633Sdim PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const { 225226633Sdim return PDC ? PDC->getGenerationScheme() : PathDiagnosticConsumer::Extensive; 226218887Sdim } 227218887Sdim 228218887Sdim bool supportsLogicalOpControlFlow() const { 229218887Sdim return PDC ? PDC->supportsLogicalOpControlFlow() : true; 230218887Sdim } 231218887Sdim}; 232218887Sdim} // end anonymous namespace 233218887Sdim 234218887SdimPathDiagnosticLocation 235226633SdimPathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) { 236218887Sdim if (const Stmt *S = GetNextStmt(N)) 237234353Sdim return PathDiagnosticLocation(S, getSourceManager(), LC); 238218887Sdim 239226633Sdim return PathDiagnosticLocation::createDeclEnd(N->getLocationContext(), 240226633Sdim getSourceManager()); 241218887Sdim} 242218887Sdim 243218887SdimPathDiagnosticLocation 244226633SdimPathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os, 245226633Sdim const ExplodedNode *N) { 246218887Sdim 247218887Sdim // Slow, but probably doesn't matter. 248218887Sdim if (os.str().empty()) 249218887Sdim os << ' '; 250218887Sdim 251218887Sdim const PathDiagnosticLocation &Loc = ExecutionContinues(N); 252218887Sdim 253218887Sdim if (Loc.asStmt()) 254218887Sdim os << "Execution continues on line " 255226633Sdim << getSourceManager().getExpansionLineNumber(Loc.asLocation()) 256218887Sdim << '.'; 257218887Sdim else { 258218887Sdim os << "Execution jumps to the end of the "; 259218887Sdim const Decl *D = N->getLocationContext()->getDecl(); 260218887Sdim if (isa<ObjCMethodDecl>(D)) 261218887Sdim os << "method"; 262218887Sdim else if (isa<FunctionDecl>(D)) 263218887Sdim os << "function"; 264218887Sdim else { 265218887Sdim assert(isa<BlockDecl>(D)); 266218887Sdim os << "anonymous block"; 267218887Sdim } 268218887Sdim os << '.'; 269218887Sdim } 270218887Sdim 271218887Sdim return Loc; 272218887Sdim} 273218887Sdim 274218887Sdimstatic bool IsNested(const Stmt *S, ParentMap &PM) { 275218887Sdim if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S))) 276218887Sdim return true; 277218887Sdim 278218887Sdim const Stmt *Parent = PM.getParentIgnoreParens(S); 279218887Sdim 280218887Sdim if (Parent) 281218887Sdim switch (Parent->getStmtClass()) { 282218887Sdim case Stmt::ForStmtClass: 283218887Sdim case Stmt::DoStmtClass: 284218887Sdim case Stmt::WhileStmtClass: 285218887Sdim return true; 286218887Sdim default: 287218887Sdim break; 288218887Sdim } 289218887Sdim 290218887Sdim return false; 291218887Sdim} 292218887Sdim 293218887SdimPathDiagnosticLocation 294218887SdimPathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { 295226633Sdim assert(S && "Null Stmt *passed to getEnclosingStmtLocation"); 296218887Sdim ParentMap &P = getParentMap(); 297218887Sdim SourceManager &SMgr = getSourceManager(); 298218887Sdim 299218887Sdim while (IsNested(S, P)) { 300218887Sdim const Stmt *Parent = P.getParentIgnoreParens(S); 301218887Sdim 302218887Sdim if (!Parent) 303218887Sdim break; 304218887Sdim 305218887Sdim switch (Parent->getStmtClass()) { 306218887Sdim case Stmt::BinaryOperatorClass: { 307218887Sdim const BinaryOperator *B = cast<BinaryOperator>(Parent); 308218887Sdim if (B->isLogicalOp()) 309226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 310218887Sdim break; 311218887Sdim } 312218887Sdim case Stmt::CompoundStmtClass: 313218887Sdim case Stmt::StmtExprClass: 314226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 315218887Sdim case Stmt::ChooseExprClass: 316218887Sdim // Similar to '?' if we are referring to condition, just have the edge 317218887Sdim // point to the entire choose expression. 318218887Sdim if (cast<ChooseExpr>(Parent)->getCond() == S) 319226633Sdim return PathDiagnosticLocation(Parent, SMgr, LC); 320218887Sdim else 321226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 322218887Sdim case Stmt::BinaryConditionalOperatorClass: 323218887Sdim case Stmt::ConditionalOperatorClass: 324218887Sdim // For '?', if we are referring to condition, just have the edge point 325218887Sdim // to the entire '?' expression. 326218887Sdim if (cast<AbstractConditionalOperator>(Parent)->getCond() == S) 327226633Sdim return PathDiagnosticLocation(Parent, SMgr, LC); 328218887Sdim else 329226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 330218887Sdim case Stmt::DoStmtClass: 331226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 332218887Sdim case Stmt::ForStmtClass: 333218887Sdim if (cast<ForStmt>(Parent)->getBody() == S) 334226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 335218887Sdim break; 336218887Sdim case Stmt::IfStmtClass: 337218887Sdim if (cast<IfStmt>(Parent)->getCond() != S) 338226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 339218887Sdim break; 340218887Sdim case Stmt::ObjCForCollectionStmtClass: 341218887Sdim if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S) 342226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 343218887Sdim break; 344218887Sdim case Stmt::WhileStmtClass: 345218887Sdim if (cast<WhileStmt>(Parent)->getCond() != S) 346226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 347218887Sdim break; 348218887Sdim default: 349218887Sdim break; 350218887Sdim } 351218887Sdim 352218887Sdim S = Parent; 353218887Sdim } 354218887Sdim 355218887Sdim assert(S && "Cannot have null Stmt for PathDiagnosticLocation"); 356218887Sdim 357218887Sdim // Special case: DeclStmts can appear in for statement declarations, in which 358218887Sdim // case the ForStmt is the context. 359218887Sdim if (isa<DeclStmt>(S)) { 360218887Sdim if (const Stmt *Parent = P.getParent(S)) { 361218887Sdim switch (Parent->getStmtClass()) { 362218887Sdim case Stmt::ForStmtClass: 363218887Sdim case Stmt::ObjCForCollectionStmtClass: 364226633Sdim return PathDiagnosticLocation(Parent, SMgr, LC); 365218887Sdim default: 366218887Sdim break; 367218887Sdim } 368218887Sdim } 369218887Sdim } 370218887Sdim else if (isa<BinaryOperator>(S)) { 371218887Sdim // Special case: the binary operator represents the initialization 372218887Sdim // code in a for statement (this can happen when the variable being 373218887Sdim // initialized is an old variable. 374218887Sdim if (const ForStmt *FS = 375218887Sdim dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) { 376218887Sdim if (FS->getInit() == S) 377226633Sdim return PathDiagnosticLocation(FS, SMgr, LC); 378218887Sdim } 379218887Sdim } 380218887Sdim 381226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 382218887Sdim} 383218887Sdim 384218887Sdim//===----------------------------------------------------------------------===// 385234353Sdim// "Minimal" path diagnostic generation algorithm. 386218887Sdim//===----------------------------------------------------------------------===// 387234353Sdimtypedef std::pair<PathDiagnosticCallPiece*, const ExplodedNode*> StackDiagPair; 388234353Sdimtypedef SmallVector<StackDiagPair, 6> StackDiagVector; 389218887Sdim 390234353Sdimstatic void updateStackPiecesWithMessage(PathDiagnosticPiece *P, 391234353Sdim StackDiagVector &CallStack) { 392234353Sdim // If the piece contains a special message, add it to all the call 393234353Sdim // pieces on the active stack. 394234353Sdim if (PathDiagnosticEventPiece *ep = 395234353Sdim dyn_cast<PathDiagnosticEventPiece>(P)) { 396218887Sdim 397234353Sdim if (ep->hasCallStackHint()) 398234353Sdim for (StackDiagVector::iterator I = CallStack.begin(), 399234353Sdim E = CallStack.end(); I != E; ++I) { 400234353Sdim PathDiagnosticCallPiece *CP = I->first; 401234353Sdim const ExplodedNode *N = I->second; 402234353Sdim std::string stackMsg = ep->getCallStackMessage(N); 403218887Sdim 404234353Sdim // The last message on the path to final bug is the most important 405234353Sdim // one. Since we traverse the path backwards, do not add the message 406234353Sdim // if one has been previously added. 407234353Sdim if (!CP->hasCallStackMessage()) 408234353Sdim CP->setCallStackMessage(stackMsg); 409234353Sdim } 410218887Sdim } 411218887Sdim} 412218887Sdim 413234353Sdimstatic void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM); 414218887Sdim 415218887Sdimstatic void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, 416218887Sdim PathDiagnosticBuilder &PDB, 417234353Sdim const ExplodedNode *N, 418234353Sdim ArrayRef<BugReporterVisitor *> visitors) { 419218887Sdim 420218887Sdim SourceManager& SMgr = PDB.getSourceManager(); 421234353Sdim const LocationContext *LC = PDB.LC; 422226633Sdim const ExplodedNode *NextNode = N->pred_empty() 423218887Sdim ? NULL : *(N->pred_begin()); 424234353Sdim 425234353Sdim StackDiagVector CallStack; 426234353Sdim 427218887Sdim while (NextNode) { 428218887Sdim N = NextNode; 429234353Sdim PDB.LC = N->getLocationContext(); 430218887Sdim NextNode = GetPredecessorNode(N); 431218887Sdim 432218887Sdim ProgramPoint P = N->getLocation(); 433234353Sdim 434239462Sdim if (const CallExitEnd *CE = dyn_cast<CallExitEnd>(&P)) { 435234353Sdim PathDiagnosticCallPiece *C = 436234353Sdim PathDiagnosticCallPiece::construct(N, *CE, SMgr); 437234353Sdim PD.getActivePath().push_front(C); 438234353Sdim PD.pushActivePath(&C->path); 439234353Sdim CallStack.push_back(StackDiagPair(C, N)); 440234353Sdim continue; 441234353Sdim } 442234353Sdim 443234353Sdim if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) { 444239462Sdim // Flush all locations, and pop the active path. 445239462Sdim bool VisitedEntireCall = PD.isWithinCall(); 446234353Sdim PD.popActivePath(); 447239462Sdim 448239462Sdim // Either we just added a bunch of stuff to the top-level path, or 449239462Sdim // we have a previous CallExitEnd. If the former, it means that the 450234353Sdim // path terminated within a function call. We must then take the 451234353Sdim // current contents of the active path and place it within 452234353Sdim // a new PathDiagnosticCallPiece. 453239462Sdim PathDiagnosticCallPiece *C; 454239462Sdim if (VisitedEntireCall) { 455239462Sdim C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); 456239462Sdim } else { 457234353Sdim const Decl *Caller = CE->getLocationContext()->getDecl(); 458234353Sdim C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 459234353Sdim } 460239462Sdim 461234353Sdim C->setCallee(*CE, SMgr); 462234353Sdim if (!CallStack.empty()) { 463234353Sdim assert(CallStack.back().first == C); 464234353Sdim CallStack.pop_back(); 465234353Sdim } 466234353Sdim continue; 467234353Sdim } 468218887Sdim 469226633Sdim if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { 470226633Sdim const CFGBlock *Src = BE->getSrc(); 471226633Sdim const CFGBlock *Dst = BE->getDst(); 472226633Sdim const Stmt *T = Src->getTerminator(); 473218887Sdim 474218887Sdim if (!T) 475218887Sdim continue; 476218887Sdim 477226633Sdim PathDiagnosticLocation Start = 478226633Sdim PathDiagnosticLocation::createBegin(T, SMgr, 479226633Sdim N->getLocationContext()); 480218887Sdim 481218887Sdim switch (T->getStmtClass()) { 482218887Sdim default: 483218887Sdim break; 484218887Sdim 485218887Sdim case Stmt::GotoStmtClass: 486218887Sdim case Stmt::IndirectGotoStmtClass: { 487226633Sdim const Stmt *S = GetNextStmt(N); 488218887Sdim 489218887Sdim if (!S) 490218887Sdim continue; 491218887Sdim 492218887Sdim std::string sbuf; 493218887Sdim llvm::raw_string_ostream os(sbuf); 494218887Sdim const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S); 495218887Sdim 496218887Sdim os << "Control jumps to line " 497226633Sdim << End.asLocation().getExpansionLineNumber(); 498234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 499234353Sdim os.str())); 500218887Sdim break; 501218887Sdim } 502218887Sdim 503218887Sdim case Stmt::SwitchStmtClass: { 504218887Sdim // Figure out what case arm we took. 505218887Sdim std::string sbuf; 506218887Sdim llvm::raw_string_ostream os(sbuf); 507218887Sdim 508226633Sdim if (const Stmt *S = Dst->getLabel()) { 509226633Sdim PathDiagnosticLocation End(S, SMgr, LC); 510218887Sdim 511218887Sdim switch (S->getStmtClass()) { 512218887Sdim default: 513218887Sdim os << "No cases match in the switch statement. " 514218887Sdim "Control jumps to line " 515226633Sdim << End.asLocation().getExpansionLineNumber(); 516218887Sdim break; 517218887Sdim case Stmt::DefaultStmtClass: 518218887Sdim os << "Control jumps to the 'default' case at line " 519226633Sdim << End.asLocation().getExpansionLineNumber(); 520218887Sdim break; 521218887Sdim 522218887Sdim case Stmt::CaseStmtClass: { 523218887Sdim os << "Control jumps to 'case "; 524226633Sdim const CaseStmt *Case = cast<CaseStmt>(S); 525226633Sdim const Expr *LHS = Case->getLHS()->IgnoreParenCasts(); 526218887Sdim 527218887Sdim // Determine if it is an enum. 528218887Sdim bool GetRawInt = true; 529218887Sdim 530226633Sdim if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) { 531218887Sdim // FIXME: Maybe this should be an assertion. Are there cases 532218887Sdim // were it is not an EnumConstantDecl? 533226633Sdim const EnumConstantDecl *D = 534218887Sdim dyn_cast<EnumConstantDecl>(DR->getDecl()); 535218887Sdim 536218887Sdim if (D) { 537218887Sdim GetRawInt = false; 538226633Sdim os << *D; 539218887Sdim } 540218887Sdim } 541218887Sdim 542218887Sdim if (GetRawInt) 543226633Sdim os << LHS->EvaluateKnownConstInt(PDB.getASTContext()); 544218887Sdim 545218887Sdim os << ":' at line " 546226633Sdim << End.asLocation().getExpansionLineNumber(); 547218887Sdim break; 548218887Sdim } 549218887Sdim } 550234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 551218887Sdim os.str())); 552218887Sdim } 553218887Sdim else { 554218887Sdim os << "'Default' branch taken. "; 555218887Sdim const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N); 556234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 557218887Sdim os.str())); 558218887Sdim } 559218887Sdim 560218887Sdim break; 561218887Sdim } 562218887Sdim 563218887Sdim case Stmt::BreakStmtClass: 564218887Sdim case Stmt::ContinueStmtClass: { 565218887Sdim std::string sbuf; 566218887Sdim llvm::raw_string_ostream os(sbuf); 567218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 568234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 569218887Sdim os.str())); 570218887Sdim break; 571218887Sdim } 572218887Sdim 573218887Sdim // Determine control-flow for ternary '?'. 574218887Sdim case Stmt::BinaryConditionalOperatorClass: 575218887Sdim case Stmt::ConditionalOperatorClass: { 576218887Sdim std::string sbuf; 577218887Sdim llvm::raw_string_ostream os(sbuf); 578218887Sdim os << "'?' condition is "; 579218887Sdim 580218887Sdim if (*(Src->succ_begin()+1) == Dst) 581218887Sdim os << "false"; 582218887Sdim else 583218887Sdim os << "true"; 584218887Sdim 585218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 586218887Sdim 587218887Sdim if (const Stmt *S = End.asStmt()) 588218887Sdim End = PDB.getEnclosingStmtLocation(S); 589218887Sdim 590234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 591218887Sdim os.str())); 592218887Sdim break; 593218887Sdim } 594218887Sdim 595218887Sdim // Determine control-flow for short-circuited '&&' and '||'. 596218887Sdim case Stmt::BinaryOperatorClass: { 597218887Sdim if (!PDB.supportsLogicalOpControlFlow()) 598218887Sdim break; 599218887Sdim 600218887Sdim const BinaryOperator *B = cast<BinaryOperator>(T); 601218887Sdim std::string sbuf; 602218887Sdim llvm::raw_string_ostream os(sbuf); 603218887Sdim os << "Left side of '"; 604218887Sdim 605218887Sdim if (B->getOpcode() == BO_LAnd) { 606218887Sdim os << "&&" << "' is "; 607218887Sdim 608218887Sdim if (*(Src->succ_begin()+1) == Dst) { 609218887Sdim os << "false"; 610226633Sdim PathDiagnosticLocation End(B->getLHS(), SMgr, LC); 611226633Sdim PathDiagnosticLocation Start = 612226633Sdim PathDiagnosticLocation::createOperatorLoc(B, SMgr); 613234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 614218887Sdim os.str())); 615218887Sdim } 616218887Sdim else { 617218887Sdim os << "true"; 618226633Sdim PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); 619218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 620234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 621218887Sdim os.str())); 622218887Sdim } 623218887Sdim } 624218887Sdim else { 625218887Sdim assert(B->getOpcode() == BO_LOr); 626218887Sdim os << "||" << "' is "; 627218887Sdim 628218887Sdim if (*(Src->succ_begin()+1) == Dst) { 629218887Sdim os << "false"; 630226633Sdim PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); 631218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 632234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 633218887Sdim os.str())); 634218887Sdim } 635218887Sdim else { 636218887Sdim os << "true"; 637226633Sdim PathDiagnosticLocation End(B->getLHS(), SMgr, LC); 638226633Sdim PathDiagnosticLocation Start = 639226633Sdim PathDiagnosticLocation::createOperatorLoc(B, SMgr); 640234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 641218887Sdim os.str())); 642218887Sdim } 643218887Sdim } 644218887Sdim 645218887Sdim break; 646218887Sdim } 647218887Sdim 648218887Sdim case Stmt::DoStmtClass: { 649218887Sdim if (*(Src->succ_begin()) == Dst) { 650218887Sdim std::string sbuf; 651218887Sdim llvm::raw_string_ostream os(sbuf); 652218887Sdim 653218887Sdim os << "Loop condition is true. "; 654218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 655218887Sdim 656218887Sdim if (const Stmt *S = End.asStmt()) 657218887Sdim End = PDB.getEnclosingStmtLocation(S); 658218887Sdim 659234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 660218887Sdim os.str())); 661218887Sdim } 662218887Sdim else { 663218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 664218887Sdim 665218887Sdim if (const Stmt *S = End.asStmt()) 666218887Sdim End = PDB.getEnclosingStmtLocation(S); 667218887Sdim 668234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 669218887Sdim "Loop condition is false. Exiting loop")); 670218887Sdim } 671218887Sdim 672218887Sdim break; 673218887Sdim } 674218887Sdim 675218887Sdim case Stmt::WhileStmtClass: 676218887Sdim case Stmt::ForStmtClass: { 677218887Sdim if (*(Src->succ_begin()+1) == Dst) { 678218887Sdim std::string sbuf; 679218887Sdim llvm::raw_string_ostream os(sbuf); 680218887Sdim 681218887Sdim os << "Loop condition is false. "; 682218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 683218887Sdim if (const Stmt *S = End.asStmt()) 684218887Sdim End = PDB.getEnclosingStmtLocation(S); 685218887Sdim 686234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 687218887Sdim os.str())); 688218887Sdim } 689218887Sdim else { 690218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 691218887Sdim if (const Stmt *S = End.asStmt()) 692218887Sdim End = PDB.getEnclosingStmtLocation(S); 693218887Sdim 694234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 695218887Sdim "Loop condition is true. Entering loop body")); 696218887Sdim } 697218887Sdim 698218887Sdim break; 699218887Sdim } 700218887Sdim 701218887Sdim case Stmt::IfStmtClass: { 702218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 703218887Sdim 704218887Sdim if (const Stmt *S = End.asStmt()) 705218887Sdim End = PDB.getEnclosingStmtLocation(S); 706218887Sdim 707218887Sdim if (*(Src->succ_begin()+1) == Dst) 708234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 709218887Sdim "Taking false branch")); 710218887Sdim else 711234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, 712218887Sdim "Taking true branch")); 713218887Sdim 714218887Sdim break; 715218887Sdim } 716218887Sdim } 717218887Sdim } 718218887Sdim 719218887Sdim if (NextNode) { 720226633Sdim // Add diagnostic pieces from custom visitors. 721226633Sdim BugReport *R = PDB.getBugReport(); 722234353Sdim for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(), 723234353Sdim E = visitors.end(); 724234353Sdim I != E; ++I) { 725234353Sdim if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) { 726234353Sdim PD.getActivePath().push_front(p); 727234353Sdim updateStackPiecesWithMessage(p, CallStack); 728234353Sdim } 729218887Sdim } 730218887Sdim } 731218887Sdim } 732218887Sdim 733218887Sdim // After constructing the full PathDiagnostic, do a pass over it to compact 734218887Sdim // PathDiagnosticPieces that occur within a macro. 735234353Sdim CompactPathDiagnostic(PD.getMutablePieces(), PDB.getSourceManager()); 736218887Sdim} 737218887Sdim 738218887Sdim//===----------------------------------------------------------------------===// 739218887Sdim// "Extensive" PathDiagnostic generation. 740218887Sdim//===----------------------------------------------------------------------===// 741218887Sdim 742218887Sdimstatic bool IsControlFlowExpr(const Stmt *S) { 743218887Sdim const Expr *E = dyn_cast<Expr>(S); 744218887Sdim 745218887Sdim if (!E) 746218887Sdim return false; 747218887Sdim 748218887Sdim E = E->IgnoreParenCasts(); 749218887Sdim 750218887Sdim if (isa<AbstractConditionalOperator>(E)) 751218887Sdim return true; 752218887Sdim 753218887Sdim if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E)) 754218887Sdim if (B->isLogicalOp()) 755218887Sdim return true; 756218887Sdim 757218887Sdim return false; 758218887Sdim} 759218887Sdim 760218887Sdimnamespace { 761218887Sdimclass ContextLocation : public PathDiagnosticLocation { 762218887Sdim bool IsDead; 763218887Sdimpublic: 764218887Sdim ContextLocation(const PathDiagnosticLocation &L, bool isdead = false) 765218887Sdim : PathDiagnosticLocation(L), IsDead(isdead) {} 766218887Sdim 767218887Sdim void markDead() { IsDead = true; } 768218887Sdim bool isDead() const { return IsDead; } 769218887Sdim}; 770218887Sdim 771218887Sdimclass EdgeBuilder { 772218887Sdim std::vector<ContextLocation> CLocs; 773218887Sdim typedef std::vector<ContextLocation>::iterator iterator; 774218887Sdim PathDiagnostic &PD; 775218887Sdim PathDiagnosticBuilder &PDB; 776218887Sdim PathDiagnosticLocation PrevLoc; 777218887Sdim 778218887Sdim bool IsConsumedExpr(const PathDiagnosticLocation &L); 779218887Sdim 780218887Sdim bool containsLocation(const PathDiagnosticLocation &Container, 781218887Sdim const PathDiagnosticLocation &Containee); 782218887Sdim 783218887Sdim PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L); 784218887Sdim 785218887Sdim PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L, 786218887Sdim bool firstCharOnly = false) { 787218887Sdim if (const Stmt *S = L.asStmt()) { 788218887Sdim const Stmt *Original = S; 789218887Sdim while (1) { 790218887Sdim // Adjust the location for some expressions that are best referenced 791218887Sdim // by one of their subexpressions. 792218887Sdim switch (S->getStmtClass()) { 793218887Sdim default: 794218887Sdim break; 795218887Sdim case Stmt::ParenExprClass: 796221345Sdim case Stmt::GenericSelectionExprClass: 797221345Sdim S = cast<Expr>(S)->IgnoreParens(); 798218887Sdim firstCharOnly = true; 799218887Sdim continue; 800218887Sdim case Stmt::BinaryConditionalOperatorClass: 801218887Sdim case Stmt::ConditionalOperatorClass: 802218887Sdim S = cast<AbstractConditionalOperator>(S)->getCond(); 803218887Sdim firstCharOnly = true; 804218887Sdim continue; 805218887Sdim case Stmt::ChooseExprClass: 806218887Sdim S = cast<ChooseExpr>(S)->getCond(); 807218887Sdim firstCharOnly = true; 808218887Sdim continue; 809218887Sdim case Stmt::BinaryOperatorClass: 810218887Sdim S = cast<BinaryOperator>(S)->getLHS(); 811218887Sdim firstCharOnly = true; 812218887Sdim continue; 813218887Sdim } 814218887Sdim 815218887Sdim break; 816218887Sdim } 817218887Sdim 818218887Sdim if (S != Original) 819234353Sdim L = PathDiagnosticLocation(S, L.getManager(), PDB.LC); 820218887Sdim } 821218887Sdim 822218887Sdim if (firstCharOnly) 823226633Sdim L = PathDiagnosticLocation::createSingleLocation(L); 824218887Sdim 825218887Sdim return L; 826218887Sdim } 827218887Sdim 828218887Sdim void popLocation() { 829218887Sdim if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) { 830218887Sdim // For contexts, we only one the first character as the range. 831218887Sdim rawAddEdge(cleanUpLocation(CLocs.back(), true)); 832218887Sdim } 833218887Sdim CLocs.pop_back(); 834218887Sdim } 835218887Sdim 836218887Sdimpublic: 837218887Sdim EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb) 838218887Sdim : PD(pd), PDB(pdb) { 839218887Sdim 840218887Sdim // If the PathDiagnostic already has pieces, add the enclosing statement 841218887Sdim // of the first piece as a context as well. 842234353Sdim if (!PD.path.empty()) { 843234353Sdim PrevLoc = (*PD.path.begin())->getLocation(); 844218887Sdim 845218887Sdim if (const Stmt *S = PrevLoc.asStmt()) 846218887Sdim addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 847218887Sdim } 848218887Sdim } 849218887Sdim 850218887Sdim ~EdgeBuilder() { 851218887Sdim while (!CLocs.empty()) popLocation(); 852226633Sdim 853218887Sdim // Finally, add an initial edge from the start location of the first 854218887Sdim // statement (if it doesn't already exist). 855226633Sdim PathDiagnosticLocation L = PathDiagnosticLocation::createDeclBegin( 856234353Sdim PDB.LC, 857226633Sdim PDB.getSourceManager()); 858226633Sdim if (L.isValid()) 859226633Sdim rawAddEdge(L); 860218887Sdim } 861218887Sdim 862234353Sdim void flushLocations() { 863234353Sdim while (!CLocs.empty()) 864234353Sdim popLocation(); 865234353Sdim PrevLoc = PathDiagnosticLocation(); 866234353Sdim } 867234353Sdim 868218887Sdim void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false); 869218887Sdim 870218887Sdim void rawAddEdge(PathDiagnosticLocation NewLoc); 871218887Sdim 872218887Sdim void addContext(const Stmt *S); 873239462Sdim void addContext(const PathDiagnosticLocation &L); 874218887Sdim void addExtendedContext(const Stmt *S); 875218887Sdim}; 876218887Sdim} // end anonymous namespace 877218887Sdim 878218887Sdim 879218887SdimPathDiagnosticLocation 880218887SdimEdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) { 881218887Sdim if (const Stmt *S = L.asStmt()) { 882218887Sdim if (IsControlFlowExpr(S)) 883218887Sdim return L; 884218887Sdim 885218887Sdim return PDB.getEnclosingStmtLocation(S); 886218887Sdim } 887218887Sdim 888218887Sdim return L; 889218887Sdim} 890218887Sdim 891218887Sdimbool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container, 892218887Sdim const PathDiagnosticLocation &Containee) { 893218887Sdim 894218887Sdim if (Container == Containee) 895218887Sdim return true; 896218887Sdim 897218887Sdim if (Container.asDecl()) 898218887Sdim return true; 899218887Sdim 900218887Sdim if (const Stmt *S = Containee.asStmt()) 901218887Sdim if (const Stmt *ContainerS = Container.asStmt()) { 902218887Sdim while (S) { 903218887Sdim if (S == ContainerS) 904218887Sdim return true; 905218887Sdim S = PDB.getParent(S); 906218887Sdim } 907218887Sdim return false; 908218887Sdim } 909218887Sdim 910218887Sdim // Less accurate: compare using source ranges. 911218887Sdim SourceRange ContainerR = Container.asRange(); 912218887Sdim SourceRange ContaineeR = Containee.asRange(); 913218887Sdim 914218887Sdim SourceManager &SM = PDB.getSourceManager(); 915226633Sdim SourceLocation ContainerRBeg = SM.getExpansionLoc(ContainerR.getBegin()); 916226633Sdim SourceLocation ContainerREnd = SM.getExpansionLoc(ContainerR.getEnd()); 917226633Sdim SourceLocation ContaineeRBeg = SM.getExpansionLoc(ContaineeR.getBegin()); 918226633Sdim SourceLocation ContaineeREnd = SM.getExpansionLoc(ContaineeR.getEnd()); 919218887Sdim 920226633Sdim unsigned ContainerBegLine = SM.getExpansionLineNumber(ContainerRBeg); 921226633Sdim unsigned ContainerEndLine = SM.getExpansionLineNumber(ContainerREnd); 922226633Sdim unsigned ContaineeBegLine = SM.getExpansionLineNumber(ContaineeRBeg); 923226633Sdim unsigned ContaineeEndLine = SM.getExpansionLineNumber(ContaineeREnd); 924218887Sdim 925218887Sdim assert(ContainerBegLine <= ContainerEndLine); 926218887Sdim assert(ContaineeBegLine <= ContaineeEndLine); 927218887Sdim 928218887Sdim return (ContainerBegLine <= ContaineeBegLine && 929218887Sdim ContainerEndLine >= ContaineeEndLine && 930218887Sdim (ContainerBegLine != ContaineeBegLine || 931226633Sdim SM.getExpansionColumnNumber(ContainerRBeg) <= 932226633Sdim SM.getExpansionColumnNumber(ContaineeRBeg)) && 933218887Sdim (ContainerEndLine != ContaineeEndLine || 934226633Sdim SM.getExpansionColumnNumber(ContainerREnd) >= 935234353Sdim SM.getExpansionColumnNumber(ContaineeREnd))); 936218887Sdim} 937218887Sdim 938218887Sdimvoid EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) { 939218887Sdim if (!PrevLoc.isValid()) { 940218887Sdim PrevLoc = NewLoc; 941218887Sdim return; 942218887Sdim } 943218887Sdim 944218887Sdim const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc); 945218887Sdim const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc); 946218887Sdim 947218887Sdim if (NewLocClean.asLocation() == PrevLocClean.asLocation()) 948218887Sdim return; 949218887Sdim 950218887Sdim // FIXME: Ignore intra-macro edges for now. 951226633Sdim if (NewLocClean.asLocation().getExpansionLoc() == 952226633Sdim PrevLocClean.asLocation().getExpansionLoc()) 953218887Sdim return; 954218887Sdim 955234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean)); 956218887Sdim PrevLoc = NewLoc; 957218887Sdim} 958218887Sdim 959218887Sdimvoid EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd) { 960218887Sdim 961218887Sdim if (!alwaysAdd && NewLoc.asLocation().isMacroID()) 962218887Sdim return; 963218887Sdim 964218887Sdim const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc); 965218887Sdim 966218887Sdim while (!CLocs.empty()) { 967218887Sdim ContextLocation &TopContextLoc = CLocs.back(); 968218887Sdim 969218887Sdim // Is the top location context the same as the one for the new location? 970218887Sdim if (TopContextLoc == CLoc) { 971218887Sdim if (alwaysAdd) { 972218887Sdim if (IsConsumedExpr(TopContextLoc) && 973218887Sdim !IsControlFlowExpr(TopContextLoc.asStmt())) 974218887Sdim TopContextLoc.markDead(); 975218887Sdim 976218887Sdim rawAddEdge(NewLoc); 977218887Sdim } 978218887Sdim 979218887Sdim return; 980218887Sdim } 981218887Sdim 982218887Sdim if (containsLocation(TopContextLoc, CLoc)) { 983218887Sdim if (alwaysAdd) { 984218887Sdim rawAddEdge(NewLoc); 985218887Sdim 986218887Sdim if (IsConsumedExpr(CLoc) && !IsControlFlowExpr(CLoc.asStmt())) { 987218887Sdim CLocs.push_back(ContextLocation(CLoc, true)); 988218887Sdim return; 989218887Sdim } 990218887Sdim } 991218887Sdim 992218887Sdim CLocs.push_back(CLoc); 993218887Sdim return; 994218887Sdim } 995218887Sdim 996218887Sdim // Context does not contain the location. Flush it. 997218887Sdim popLocation(); 998218887Sdim } 999218887Sdim 1000218887Sdim // If we reach here, there is no enclosing context. Just add the edge. 1001218887Sdim rawAddEdge(NewLoc); 1002218887Sdim} 1003218887Sdim 1004218887Sdimbool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) { 1005218887Sdim if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt())) 1006218887Sdim return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X); 1007218887Sdim 1008218887Sdim return false; 1009218887Sdim} 1010218887Sdim 1011218887Sdimvoid EdgeBuilder::addExtendedContext(const Stmt *S) { 1012218887Sdim if (!S) 1013218887Sdim return; 1014218887Sdim 1015218887Sdim const Stmt *Parent = PDB.getParent(S); 1016218887Sdim while (Parent) { 1017218887Sdim if (isa<CompoundStmt>(Parent)) 1018218887Sdim Parent = PDB.getParent(Parent); 1019218887Sdim else 1020218887Sdim break; 1021218887Sdim } 1022218887Sdim 1023218887Sdim if (Parent) { 1024218887Sdim switch (Parent->getStmtClass()) { 1025218887Sdim case Stmt::DoStmtClass: 1026218887Sdim case Stmt::ObjCAtSynchronizedStmtClass: 1027218887Sdim addContext(Parent); 1028218887Sdim default: 1029218887Sdim break; 1030218887Sdim } 1031218887Sdim } 1032218887Sdim 1033218887Sdim addContext(S); 1034218887Sdim} 1035218887Sdim 1036218887Sdimvoid EdgeBuilder::addContext(const Stmt *S) { 1037218887Sdim if (!S) 1038218887Sdim return; 1039218887Sdim 1040234353Sdim PathDiagnosticLocation L(S, PDB.getSourceManager(), PDB.LC); 1041239462Sdim addContext(L); 1042239462Sdim} 1043218887Sdim 1044239462Sdimvoid EdgeBuilder::addContext(const PathDiagnosticLocation &L) { 1045218887Sdim while (!CLocs.empty()) { 1046218887Sdim const PathDiagnosticLocation &TopContextLoc = CLocs.back(); 1047218887Sdim 1048218887Sdim // Is the top location context the same as the one for the new location? 1049218887Sdim if (TopContextLoc == L) 1050218887Sdim return; 1051218887Sdim 1052218887Sdim if (containsLocation(TopContextLoc, L)) { 1053218887Sdim CLocs.push_back(L); 1054218887Sdim return; 1055218887Sdim } 1056218887Sdim 1057218887Sdim // Context does not contain the location. Flush it. 1058218887Sdim popLocation(); 1059218887Sdim } 1060218887Sdim 1061218887Sdim CLocs.push_back(L); 1062218887Sdim} 1063218887Sdim 1064239462Sdim// Cone-of-influence: support the reverse propagation of "interesting" symbols 1065239462Sdim// and values by tracing interesting calculations backwards through evaluated 1066239462Sdim// expressions along a path. This is probably overly complicated, but the idea 1067239462Sdim// is that if an expression computed an "interesting" value, the child 1068239462Sdim// expressions are are also likely to be "interesting" as well (which then 1069239462Sdim// propagates to the values they in turn compute). This reverse propagation 1070239462Sdim// is needed to track interesting correlations across function call boundaries, 1071239462Sdim// where formal arguments bind to actual arguments, etc. This is also needed 1072239462Sdim// because the constraint solver sometimes simplifies certain symbolic values 1073239462Sdim// into constants when appropriate, and this complicates reasoning about 1074239462Sdim// interesting values. 1075239462Sdimtypedef llvm::DenseSet<const Expr *> InterestingExprs; 1076239462Sdim 1077239462Sdimstatic void reversePropagateIntererstingSymbols(BugReport &R, 1078239462Sdim InterestingExprs &IE, 1079239462Sdim const ProgramState *State, 1080239462Sdim const Expr *Ex, 1081239462Sdim const LocationContext *LCtx) { 1082239462Sdim SVal V = State->getSVal(Ex, LCtx); 1083239462Sdim if (!(R.isInteresting(V) || IE.count(Ex))) 1084239462Sdim return; 1085239462Sdim 1086239462Sdim switch (Ex->getStmtClass()) { 1087239462Sdim default: 1088239462Sdim if (!isa<CastExpr>(Ex)) 1089239462Sdim break; 1090239462Sdim // Fall through. 1091239462Sdim case Stmt::BinaryOperatorClass: 1092239462Sdim case Stmt::UnaryOperatorClass: { 1093239462Sdim for (Stmt::const_child_iterator CI = Ex->child_begin(), 1094239462Sdim CE = Ex->child_end(); 1095239462Sdim CI != CE; ++CI) { 1096239462Sdim if (const Expr *child = dyn_cast_or_null<Expr>(*CI)) { 1097239462Sdim IE.insert(child); 1098239462Sdim SVal ChildV = State->getSVal(child, LCtx); 1099239462Sdim R.markInteresting(ChildV); 1100239462Sdim } 1101239462Sdim break; 1102239462Sdim } 1103239462Sdim } 1104239462Sdim } 1105239462Sdim 1106239462Sdim R.markInteresting(V); 1107239462Sdim} 1108239462Sdim 1109239462Sdimstatic void reversePropagateInterestingSymbols(BugReport &R, 1110239462Sdim InterestingExprs &IE, 1111239462Sdim const ProgramState *State, 1112239462Sdim const LocationContext *CalleeCtx, 1113239462Sdim const LocationContext *CallerCtx) 1114239462Sdim{ 1115239462Sdim // FIXME: Handle non-CallExpr-based CallEvents. 1116239462Sdim const StackFrameContext *Callee = CalleeCtx->getCurrentStackFrame(); 1117239462Sdim const Stmt *CallSite = Callee->getCallSite(); 1118239462Sdim if (const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite)) { 1119239462Sdim if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CalleeCtx->getDecl())) { 1120239462Sdim FunctionDecl::param_const_iterator PI = FD->param_begin(), 1121239462Sdim PE = FD->param_end(); 1122239462Sdim CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end(); 1123239462Sdim for (; AI != AE && PI != PE; ++AI, ++PI) { 1124239462Sdim if (const Expr *ArgE = *AI) { 1125239462Sdim if (const ParmVarDecl *PD = *PI) { 1126239462Sdim Loc LV = State->getLValue(PD, CalleeCtx); 1127239462Sdim if (R.isInteresting(LV) || R.isInteresting(State->getRawSVal(LV))) 1128239462Sdim IE.insert(ArgE); 1129239462Sdim } 1130239462Sdim } 1131239462Sdim } 1132239462Sdim } 1133239462Sdim } 1134239462Sdim} 1135239462Sdim 1136218887Sdimstatic void GenerateExtensivePathDiagnostic(PathDiagnostic& PD, 1137218887Sdim PathDiagnosticBuilder &PDB, 1138234353Sdim const ExplodedNode *N, 1139234353Sdim ArrayRef<BugReporterVisitor *> visitors) { 1140218887Sdim EdgeBuilder EB(PD, PDB); 1141226633Sdim const SourceManager& SM = PDB.getSourceManager(); 1142234353Sdim StackDiagVector CallStack; 1143239462Sdim InterestingExprs IE; 1144218887Sdim 1145226633Sdim const ExplodedNode *NextNode = N->pred_empty() ? NULL : *(N->pred_begin()); 1146218887Sdim while (NextNode) { 1147218887Sdim N = NextNode; 1148218887Sdim NextNode = GetPredecessorNode(N); 1149218887Sdim ProgramPoint P = N->getLocation(); 1150218887Sdim 1151218887Sdim do { 1152239462Sdim if (const PostStmt *PS = dyn_cast<PostStmt>(&P)) { 1153239462Sdim if (const Expr *Ex = PS->getStmtAs<Expr>()) 1154239462Sdim reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1155239462Sdim N->getState().getPtr(), Ex, 1156239462Sdim N->getLocationContext()); 1157239462Sdim } 1158239462Sdim 1159239462Sdim if (const CallExitEnd *CE = dyn_cast<CallExitEnd>(&P)) { 1160239462Sdim const Stmt *S = CE->getCalleeContext()->getCallSite(); 1161239462Sdim if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) { 1162239462Sdim reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1163239462Sdim N->getState().getPtr(), Ex, 1164239462Sdim N->getLocationContext()); 1165239462Sdim } 1166239462Sdim 1167234353Sdim PathDiagnosticCallPiece *C = 1168234353Sdim PathDiagnosticCallPiece::construct(N, *CE, SM); 1169239462Sdim 1170239462Sdim EB.addEdge(C->callReturn, true); 1171239462Sdim EB.flushLocations(); 1172239462Sdim 1173234353Sdim PD.getActivePath().push_front(C); 1174234353Sdim PD.pushActivePath(&C->path); 1175234353Sdim CallStack.push_back(StackDiagPair(C, N)); 1176234353Sdim break; 1177234353Sdim } 1178234353Sdim 1179234353Sdim // Pop the call hierarchy if we are done walking the contents 1180234353Sdim // of a function call. 1181234353Sdim if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) { 1182234353Sdim // Add an edge to the start of the function. 1183234353Sdim const Decl *D = CE->getCalleeContext()->getDecl(); 1184234353Sdim PathDiagnosticLocation pos = 1185234353Sdim PathDiagnosticLocation::createBegin(D, SM); 1186234353Sdim EB.addEdge(pos); 1187234353Sdim 1188234353Sdim // Flush all locations, and pop the active path. 1189239462Sdim bool VisitedEntireCall = PD.isWithinCall(); 1190234353Sdim EB.flushLocations(); 1191234353Sdim PD.popActivePath(); 1192234353Sdim PDB.LC = N->getLocationContext(); 1193234353Sdim 1194239462Sdim // Either we just added a bunch of stuff to the top-level path, or 1195239462Sdim // we have a previous CallExitEnd. If the former, it means that the 1196234353Sdim // path terminated within a function call. We must then take the 1197234353Sdim // current contents of the active path and place it within 1198234353Sdim // a new PathDiagnosticCallPiece. 1199239462Sdim PathDiagnosticCallPiece *C; 1200239462Sdim if (VisitedEntireCall) { 1201239462Sdim C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); 1202239462Sdim } else { 1203239462Sdim const Decl *Caller = CE->getLocationContext()->getDecl(); 1204234353Sdim C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 1205234353Sdim } 1206239462Sdim 1207234353Sdim C->setCallee(*CE, SM); 1208239462Sdim EB.addContext(C->getLocation()); 1209234353Sdim 1210234353Sdim if (!CallStack.empty()) { 1211234353Sdim assert(CallStack.back().first == C); 1212234353Sdim CallStack.pop_back(); 1213234353Sdim } 1214234353Sdim break; 1215234353Sdim } 1216234353Sdim 1217234353Sdim // Note that is important that we update the LocationContext 1218234353Sdim // after looking at CallExits. CallExit basically adds an 1219234353Sdim // edge in the *caller*, so we don't want to update the LocationContext 1220234353Sdim // too soon. 1221234353Sdim PDB.LC = N->getLocationContext(); 1222234353Sdim 1223218887Sdim // Block edges. 1224239462Sdim if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { 1225239462Sdim // Does this represent entering a call? If so, look at propagating 1226239462Sdim // interesting symbols across call boundaries. 1227239462Sdim if (NextNode) { 1228239462Sdim const LocationContext *CallerCtx = NextNode->getLocationContext(); 1229239462Sdim const LocationContext *CalleeCtx = PDB.LC; 1230239462Sdim if (CallerCtx != CalleeCtx) { 1231239462Sdim reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, 1232239462Sdim N->getState().getPtr(), 1233239462Sdim CalleeCtx, CallerCtx); 1234239462Sdim } 1235239462Sdim } 1236239462Sdim 1237218887Sdim const CFGBlock &Blk = *BE->getSrc(); 1238218887Sdim const Stmt *Term = Blk.getTerminator(); 1239218887Sdim 1240218887Sdim // Are we jumping to the head of a loop? Add a special diagnostic. 1241218887Sdim if (const Stmt *Loop = BE->getDst()->getLoopTarget()) { 1242234353Sdim PathDiagnosticLocation L(Loop, SM, PDB.LC); 1243218887Sdim const CompoundStmt *CS = NULL; 1244218887Sdim 1245218887Sdim if (!Term) { 1246218887Sdim if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) 1247218887Sdim CS = dyn_cast<CompoundStmt>(FS->getBody()); 1248218887Sdim else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) 1249218887Sdim CS = dyn_cast<CompoundStmt>(WS->getBody()); 1250218887Sdim } 1251218887Sdim 1252218887Sdim PathDiagnosticEventPiece *p = 1253218887Sdim new PathDiagnosticEventPiece(L, 1254218887Sdim "Looping back to the head of the loop"); 1255234353Sdim p->setPrunable(true); 1256218887Sdim 1257218887Sdim EB.addEdge(p->getLocation(), true); 1258234353Sdim PD.getActivePath().push_front(p); 1259218887Sdim 1260218887Sdim if (CS) { 1261226633Sdim PathDiagnosticLocation BL = 1262226633Sdim PathDiagnosticLocation::createEndBrace(CS, SM); 1263218887Sdim EB.addEdge(BL); 1264218887Sdim } 1265218887Sdim } 1266218887Sdim 1267218887Sdim if (Term) 1268218887Sdim EB.addContext(Term); 1269218887Sdim 1270218887Sdim break; 1271218887Sdim } 1272218887Sdim 1273218887Sdim if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) { 1274221345Sdim if (const CFGStmt *S = BE->getFirstElement().getAs<CFGStmt>()) { 1275221345Sdim const Stmt *stmt = S->getStmt(); 1276221345Sdim if (IsControlFlowExpr(stmt)) { 1277218887Sdim // Add the proper context for '&&', '||', and '?'. 1278221345Sdim EB.addContext(stmt); 1279218887Sdim } 1280218887Sdim else 1281221345Sdim EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt()); 1282218887Sdim } 1283218887Sdim 1284218887Sdim break; 1285218887Sdim } 1286234353Sdim 1287234353Sdim 1288218887Sdim } while (0); 1289218887Sdim 1290218887Sdim if (!NextNode) 1291218887Sdim continue; 1292218887Sdim 1293226633Sdim // Add pieces from custom visitors. 1294226633Sdim BugReport *R = PDB.getBugReport(); 1295234353Sdim for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(), 1296234353Sdim E = visitors.end(); 1297234353Sdim I != E; ++I) { 1298226633Sdim if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) { 1299218887Sdim const PathDiagnosticLocation &Loc = p->getLocation(); 1300218887Sdim EB.addEdge(Loc, true); 1301234353Sdim PD.getActivePath().push_front(p); 1302234353Sdim updateStackPiecesWithMessage(p, CallStack); 1303234353Sdim 1304218887Sdim if (const Stmt *S = Loc.asStmt()) 1305218887Sdim EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 1306218887Sdim } 1307218887Sdim } 1308218887Sdim } 1309218887Sdim} 1310218887Sdim 1311218887Sdim//===----------------------------------------------------------------------===// 1312218887Sdim// Methods for BugType and subclasses. 1313218887Sdim//===----------------------------------------------------------------------===// 1314219077SdimBugType::~BugType() { } 1315219077Sdim 1316218887Sdimvoid BugType::FlushReports(BugReporter &BR) {} 1317218887Sdim 1318234353Sdimvoid BuiltinBug::anchor() {} 1319234353Sdim 1320218887Sdim//===----------------------------------------------------------------------===// 1321218887Sdim// Methods for BugReport and subclasses. 1322218887Sdim//===----------------------------------------------------------------------===// 1323218887Sdim 1324234353Sdimvoid BugReport::NodeResolver::anchor() {} 1325234353Sdim 1326226633Sdimvoid BugReport::addVisitor(BugReporterVisitor* visitor) { 1327226633Sdim if (!visitor) 1328226633Sdim return; 1329226633Sdim 1330226633Sdim llvm::FoldingSetNodeID ID; 1331226633Sdim visitor->Profile(ID); 1332226633Sdim void *InsertPos; 1333226633Sdim 1334226633Sdim if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) { 1335226633Sdim delete visitor; 1336226633Sdim return; 1337226633Sdim } 1338226633Sdim 1339226633Sdim CallbacksSet.InsertNode(visitor, InsertPos); 1340234353Sdim Callbacks.push_back(visitor); 1341234353Sdim ++ConfigurationChangeToken; 1342226633Sdim} 1343226633Sdim 1344226633SdimBugReport::~BugReport() { 1345226633Sdim for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I) { 1346226633Sdim delete *I; 1347226633Sdim } 1348239462Sdim while (!interestingSymbols.empty()) { 1349239462Sdim popInterestingSymbolsAndRegions(); 1350239462Sdim } 1351226633Sdim} 1352226633Sdim 1353234353Sdimconst Decl *BugReport::getDeclWithIssue() const { 1354234353Sdim if (DeclWithIssue) 1355234353Sdim return DeclWithIssue; 1356234353Sdim 1357234353Sdim const ExplodedNode *N = getErrorNode(); 1358234353Sdim if (!N) 1359234353Sdim return 0; 1360234353Sdim 1361234353Sdim const LocationContext *LC = N->getLocationContext(); 1362234353Sdim return LC->getCurrentStackFrame()->getDecl(); 1363234353Sdim} 1364234353Sdim 1365226633Sdimvoid BugReport::Profile(llvm::FoldingSetNodeID& hash) const { 1366226633Sdim hash.AddPointer(&BT); 1367226633Sdim hash.AddString(Description); 1368234353Sdim if (UniqueingLocation.isValid()) { 1369234353Sdim UniqueingLocation.Profile(hash); 1370234353Sdim } else if (Location.isValid()) { 1371226633Sdim Location.Profile(hash); 1372226633Sdim } else { 1373226633Sdim assert(ErrorNode); 1374226633Sdim hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode)); 1375226633Sdim } 1376226633Sdim 1377226633Sdim for (SmallVectorImpl<SourceRange>::const_iterator I = 1378226633Sdim Ranges.begin(), E = Ranges.end(); I != E; ++I) { 1379226633Sdim const SourceRange range = *I; 1380226633Sdim if (!range.isValid()) 1381226633Sdim continue; 1382226633Sdim hash.AddInteger(range.getBegin().getRawEncoding()); 1383226633Sdim hash.AddInteger(range.getEnd().getRawEncoding()); 1384226633Sdim } 1385226633Sdim} 1386226633Sdim 1387234353Sdimvoid BugReport::markInteresting(SymbolRef sym) { 1388234353Sdim if (!sym) 1389234353Sdim return; 1390234353Sdim 1391234353Sdim // If the symbol wasn't already in our set, note a configuration change. 1392239462Sdim if (getInterestingSymbols().insert(sym).second) 1393234353Sdim ++ConfigurationChangeToken; 1394234353Sdim 1395234353Sdim if (const SymbolMetadata *meta = dyn_cast<SymbolMetadata>(sym)) 1396239462Sdim getInterestingRegions().insert(meta->getRegion()); 1397234353Sdim} 1398234353Sdim 1399234353Sdimvoid BugReport::markInteresting(const MemRegion *R) { 1400234353Sdim if (!R) 1401234353Sdim return; 1402234353Sdim 1403234353Sdim // If the base region wasn't already in our set, note a configuration change. 1404234353Sdim R = R->getBaseRegion(); 1405239462Sdim if (getInterestingRegions().insert(R).second) 1406234353Sdim ++ConfigurationChangeToken; 1407234353Sdim 1408234353Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 1409239462Sdim getInterestingSymbols().insert(SR->getSymbol()); 1410234353Sdim} 1411234353Sdim 1412234353Sdimvoid BugReport::markInteresting(SVal V) { 1413234353Sdim markInteresting(V.getAsRegion()); 1414234353Sdim markInteresting(V.getAsSymbol()); 1415234353Sdim} 1416234353Sdim 1417239462Sdimbool BugReport::isInteresting(SVal V) { 1418234353Sdim return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol()); 1419234353Sdim} 1420234353Sdim 1421239462Sdimbool BugReport::isInteresting(SymbolRef sym) { 1422234353Sdim if (!sym) 1423234353Sdim return false; 1424234353Sdim // We don't currently consider metadata symbols to be interesting 1425234353Sdim // even if we know their region is interesting. Is that correct behavior? 1426239462Sdim return getInterestingSymbols().count(sym); 1427234353Sdim} 1428234353Sdim 1429239462Sdimbool BugReport::isInteresting(const MemRegion *R) { 1430234353Sdim if (!R) 1431234353Sdim return false; 1432234353Sdim R = R->getBaseRegion(); 1433239462Sdim bool b = getInterestingRegions().count(R); 1434234353Sdim if (b) 1435234353Sdim return true; 1436234353Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 1437239462Sdim return getInterestingSymbols().count(SR->getSymbol()); 1438234353Sdim return false; 1439234353Sdim} 1440234353Sdim 1441239462Sdimvoid BugReport::lazyInitializeInterestingSets() { 1442239462Sdim if (interestingSymbols.empty()) { 1443239462Sdim interestingSymbols.push_back(new Symbols()); 1444239462Sdim interestingRegions.push_back(new Regions()); 1445239462Sdim } 1446239462Sdim} 1447239462Sdim 1448239462SdimBugReport::Symbols &BugReport::getInterestingSymbols() { 1449239462Sdim lazyInitializeInterestingSets(); 1450239462Sdim return *interestingSymbols.back(); 1451239462Sdim} 1452239462Sdim 1453239462SdimBugReport::Regions &BugReport::getInterestingRegions() { 1454239462Sdim lazyInitializeInterestingSets(); 1455239462Sdim return *interestingRegions.back(); 1456239462Sdim} 1457239462Sdim 1458239462Sdimvoid BugReport::pushInterestingSymbolsAndRegions() { 1459239462Sdim interestingSymbols.push_back(new Symbols(getInterestingSymbols())); 1460239462Sdim interestingRegions.push_back(new Regions(getInterestingRegions())); 1461239462Sdim} 1462239462Sdim 1463239462Sdimvoid BugReport::popInterestingSymbolsAndRegions() { 1464239462Sdim delete interestingSymbols.back(); 1465239462Sdim interestingSymbols.pop_back(); 1466239462Sdim delete interestingRegions.back(); 1467239462Sdim interestingRegions.pop_back(); 1468239462Sdim} 1469239462Sdim 1470226633Sdimconst Stmt *BugReport::getStmt() const { 1471226633Sdim if (!ErrorNode) 1472226633Sdim return 0; 1473226633Sdim 1474218887Sdim ProgramPoint ProgP = ErrorNode->getLocation(); 1475218887Sdim const Stmt *S = NULL; 1476218887Sdim 1477226633Sdim if (BlockEntrance *BE = dyn_cast<BlockEntrance>(&ProgP)) { 1478218887Sdim CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit(); 1479218887Sdim if (BE->getBlock() == &Exit) 1480218887Sdim S = GetPreviousStmt(ErrorNode); 1481218887Sdim } 1482218887Sdim if (!S) 1483218887Sdim S = GetStmt(ProgP); 1484218887Sdim 1485218887Sdim return S; 1486218887Sdim} 1487218887Sdim 1488226633Sdimstd::pair<BugReport::ranges_iterator, BugReport::ranges_iterator> 1489226633SdimBugReport::getRanges() { 1490226633Sdim // If no custom ranges, add the range of the statement corresponding to 1491226633Sdim // the error node. 1492226633Sdim if (Ranges.empty()) { 1493226633Sdim if (const Expr *E = dyn_cast_or_null<Expr>(getStmt())) 1494226633Sdim addRange(E->getSourceRange()); 1495226633Sdim else 1496226633Sdim return std::make_pair(ranges_iterator(), ranges_iterator()); 1497226633Sdim } 1498218887Sdim 1499226633Sdim // User-specified absence of range info. 1500226633Sdim if (Ranges.size() == 1 && !Ranges.begin()->isValid()) 1501226633Sdim return std::make_pair(ranges_iterator(), ranges_iterator()); 1502218887Sdim 1503226633Sdim return std::make_pair(Ranges.begin(), Ranges.end()); 1504226633Sdim} 1505218887Sdim 1506226633SdimPathDiagnosticLocation BugReport::getLocation(const SourceManager &SM) const { 1507226633Sdim if (ErrorNode) { 1508226633Sdim assert(!Location.isValid() && 1509226633Sdim "Either Location or ErrorNode should be specified but not both."); 1510218887Sdim 1511226633Sdim if (const Stmt *S = GetCurrentOrPreviousStmt(ErrorNode)) { 1512226633Sdim const LocationContext *LC = ErrorNode->getLocationContext(); 1513218887Sdim 1514218887Sdim // For member expressions, return the location of the '.' or '->'. 1515218887Sdim if (const MemberExpr *ME = dyn_cast<MemberExpr>(S)) 1516226633Sdim return PathDiagnosticLocation::createMemberLoc(ME, SM); 1517218887Sdim // For binary operators, return the location of the operator. 1518218887Sdim if (const BinaryOperator *B = dyn_cast<BinaryOperator>(S)) 1519226633Sdim return PathDiagnosticLocation::createOperatorLoc(B, SM); 1520218887Sdim 1521226633Sdim return PathDiagnosticLocation::createBegin(S, SM, LC); 1522218887Sdim } 1523226633Sdim } else { 1524226633Sdim assert(Location.isValid()); 1525226633Sdim return Location; 1526226633Sdim } 1527218887Sdim 1528226633Sdim return PathDiagnosticLocation(); 1529218887Sdim} 1530218887Sdim 1531218887Sdim//===----------------------------------------------------------------------===// 1532218887Sdim// Methods for BugReporter and subclasses. 1533218887Sdim//===----------------------------------------------------------------------===// 1534218887Sdim 1535234353SdimBugReportEquivClass::~BugReportEquivClass() { } 1536218887SdimGRBugReporter::~GRBugReporter() { } 1537218887SdimBugReporterData::~BugReporterData() {} 1538218887Sdim 1539218887SdimExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); } 1540218887Sdim 1541226633SdimProgramStateManager& 1542218887SdimGRBugReporter::getStateManager() { return Eng.getStateManager(); } 1543218887Sdim 1544226633SdimBugReporter::~BugReporter() { 1545226633Sdim FlushReports(); 1546218887Sdim 1547226633Sdim // Free the bug reports we are tracking. 1548226633Sdim typedef std::vector<BugReportEquivClass *> ContTy; 1549226633Sdim for (ContTy::iterator I = EQClassesVector.begin(), E = EQClassesVector.end(); 1550226633Sdim I != E; ++I) { 1551226633Sdim delete *I; 1552226633Sdim } 1553226633Sdim} 1554226633Sdim 1555218887Sdimvoid BugReporter::FlushReports() { 1556218887Sdim if (BugTypes.isEmpty()) 1557218887Sdim return; 1558218887Sdim 1559218887Sdim // First flush the warnings for each BugType. This may end up creating new 1560219077Sdim // warnings and new BugTypes. 1561219077Sdim // FIXME: Only NSErrorChecker needs BugType's FlushReports. 1562219077Sdim // Turn NSErrorChecker into a proper checker and remove this. 1563226633Sdim SmallVector<const BugType*, 16> bugTypes; 1564218887Sdim for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I) 1565219077Sdim bugTypes.push_back(*I); 1566226633Sdim for (SmallVector<const BugType*, 16>::iterator 1567219077Sdim I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I) 1568218887Sdim const_cast<BugType*>(*I)->FlushReports(*this); 1569218887Sdim 1570239462Sdim // We need to flush reports in deterministic order to ensure the order 1571239462Sdim // of the reports is consistent between runs. 1572239462Sdim typedef std::vector<BugReportEquivClass *> ContVecTy; 1573239462Sdim for (ContVecTy::iterator EI=EQClassesVector.begin(), EE=EQClassesVector.end(); 1574239462Sdim EI != EE; ++EI){ 1575239462Sdim BugReportEquivClass& EQ = **EI; 1576219077Sdim FlushReport(EQ); 1577219077Sdim } 1578218887Sdim 1579219077Sdim // BugReporter owns and deletes only BugTypes created implicitly through 1580219077Sdim // EmitBasicReport. 1581219077Sdim // FIXME: There are leaks from checkers that assume that the BugTypes they 1582219077Sdim // create will be destroyed by the BugReporter. 1583219077Sdim for (llvm::StringMap<BugType*>::iterator 1584219077Sdim I = StrBugTypes.begin(), E = StrBugTypes.end(); I != E; ++I) 1585219077Sdim delete I->second; 1586218887Sdim 1587218887Sdim // Remove all references to the BugType objects. 1588218887Sdim BugTypes = F.getEmptySet(); 1589218887Sdim} 1590218887Sdim 1591218887Sdim//===----------------------------------------------------------------------===// 1592218887Sdim// PathDiagnostics generation. 1593218887Sdim//===----------------------------------------------------------------------===// 1594218887Sdim 1595218887Sdimstatic std::pair<std::pair<ExplodedGraph*, NodeBackMap*>, 1596218887Sdim std::pair<ExplodedNode*, unsigned> > 1597218887SdimMakeReportGraph(const ExplodedGraph* G, 1598226633Sdim SmallVectorImpl<const ExplodedNode*> &nodes) { 1599218887Sdim 1600218887Sdim // Create the trimmed graph. It will contain the shortest paths from the 1601218887Sdim // error nodes to the root. In the new graph we should only have one 1602218887Sdim // error node unless there are two or more error nodes with the same minimum 1603218887Sdim // path length. 1604218887Sdim ExplodedGraph* GTrim; 1605218887Sdim InterExplodedGraphMap* NMap; 1606218887Sdim 1607218887Sdim llvm::DenseMap<const void*, const void*> InverseMap; 1608218887Sdim llvm::tie(GTrim, NMap) = G->Trim(nodes.data(), nodes.data() + nodes.size(), 1609218887Sdim &InverseMap); 1610218887Sdim 1611218887Sdim // Create owning pointers for GTrim and NMap just to ensure that they are 1612218887Sdim // released when this function exists. 1613234353Sdim OwningPtr<ExplodedGraph> AutoReleaseGTrim(GTrim); 1614234353Sdim OwningPtr<InterExplodedGraphMap> AutoReleaseNMap(NMap); 1615218887Sdim 1616218887Sdim // Find the (first) error node in the trimmed graph. We just need to consult 1617218887Sdim // the node map (NMap) which maps from nodes in the original graph to nodes 1618218887Sdim // in the new graph. 1619218887Sdim 1620218887Sdim std::queue<const ExplodedNode*> WS; 1621218887Sdim typedef llvm::DenseMap<const ExplodedNode*, unsigned> IndexMapTy; 1622218887Sdim IndexMapTy IndexMap; 1623218887Sdim 1624218887Sdim for (unsigned nodeIndex = 0 ; nodeIndex < nodes.size(); ++nodeIndex) { 1625218887Sdim const ExplodedNode *originalNode = nodes[nodeIndex]; 1626218887Sdim if (const ExplodedNode *N = NMap->getMappedNode(originalNode)) { 1627218887Sdim WS.push(N); 1628218887Sdim IndexMap[originalNode] = nodeIndex; 1629218887Sdim } 1630218887Sdim } 1631218887Sdim 1632218887Sdim assert(!WS.empty() && "No error node found in the trimmed graph."); 1633218887Sdim 1634218887Sdim // Create a new (third!) graph with a single path. This is the graph 1635218887Sdim // that will be returned to the caller. 1636218887Sdim ExplodedGraph *GNew = new ExplodedGraph(); 1637218887Sdim 1638218887Sdim // Sometimes the trimmed graph can contain a cycle. Perform a reverse BFS 1639218887Sdim // to the root node, and then construct a new graph that contains only 1640218887Sdim // a single path. 1641218887Sdim llvm::DenseMap<const void*,unsigned> Visited; 1642218887Sdim 1643218887Sdim unsigned cnt = 0; 1644226633Sdim const ExplodedNode *Root = 0; 1645218887Sdim 1646218887Sdim while (!WS.empty()) { 1647226633Sdim const ExplodedNode *Node = WS.front(); 1648218887Sdim WS.pop(); 1649218887Sdim 1650218887Sdim if (Visited.find(Node) != Visited.end()) 1651218887Sdim continue; 1652218887Sdim 1653218887Sdim Visited[Node] = cnt++; 1654218887Sdim 1655218887Sdim if (Node->pred_empty()) { 1656218887Sdim Root = Node; 1657218887Sdim break; 1658218887Sdim } 1659218887Sdim 1660218887Sdim for (ExplodedNode::const_pred_iterator I=Node->pred_begin(), 1661218887Sdim E=Node->pred_end(); I!=E; ++I) 1662218887Sdim WS.push(*I); 1663218887Sdim } 1664218887Sdim 1665218887Sdim assert(Root); 1666218887Sdim 1667218887Sdim // Now walk from the root down the BFS path, always taking the successor 1668218887Sdim // with the lowest number. 1669218887Sdim ExplodedNode *Last = 0, *First = 0; 1670218887Sdim NodeBackMap *BM = new NodeBackMap(); 1671218887Sdim unsigned NodeIndex = 0; 1672218887Sdim 1673218887Sdim for ( const ExplodedNode *N = Root ;;) { 1674218887Sdim // Lookup the number associated with the current node. 1675218887Sdim llvm::DenseMap<const void*,unsigned>::iterator I = Visited.find(N); 1676218887Sdim assert(I != Visited.end()); 1677218887Sdim 1678218887Sdim // Create the equivalent node in the new graph with the same state 1679218887Sdim // and location. 1680226633Sdim ExplodedNode *NewN = GNew->getNode(N->getLocation(), N->getState()); 1681218887Sdim 1682218887Sdim // Store the mapping to the original node. 1683218887Sdim llvm::DenseMap<const void*, const void*>::iterator IMitr=InverseMap.find(N); 1684218887Sdim assert(IMitr != InverseMap.end() && "No mapping to original node."); 1685218887Sdim (*BM)[NewN] = (const ExplodedNode*) IMitr->second; 1686218887Sdim 1687218887Sdim // Link up the new node with the previous node. 1688218887Sdim if (Last) 1689218887Sdim NewN->addPredecessor(Last, *GNew); 1690218887Sdim 1691218887Sdim Last = NewN; 1692218887Sdim 1693218887Sdim // Are we at the final node? 1694218887Sdim IndexMapTy::iterator IMI = 1695218887Sdim IndexMap.find((const ExplodedNode*)(IMitr->second)); 1696218887Sdim if (IMI != IndexMap.end()) { 1697218887Sdim First = NewN; 1698218887Sdim NodeIndex = IMI->second; 1699218887Sdim break; 1700218887Sdim } 1701218887Sdim 1702218887Sdim // Find the next successor node. We choose the node that is marked 1703218887Sdim // with the lowest DFS number. 1704218887Sdim ExplodedNode::const_succ_iterator SI = N->succ_begin(); 1705218887Sdim ExplodedNode::const_succ_iterator SE = N->succ_end(); 1706218887Sdim N = 0; 1707218887Sdim 1708218887Sdim for (unsigned MinVal = 0; SI != SE; ++SI) { 1709218887Sdim 1710218887Sdim I = Visited.find(*SI); 1711218887Sdim 1712218887Sdim if (I == Visited.end()) 1713218887Sdim continue; 1714218887Sdim 1715218887Sdim if (!N || I->second < MinVal) { 1716218887Sdim N = *SI; 1717218887Sdim MinVal = I->second; 1718218887Sdim } 1719218887Sdim } 1720218887Sdim 1721218887Sdim assert(N); 1722218887Sdim } 1723218887Sdim 1724218887Sdim assert(First); 1725218887Sdim 1726218887Sdim return std::make_pair(std::make_pair(GNew, BM), 1727218887Sdim std::make_pair(First, NodeIndex)); 1728218887Sdim} 1729218887Sdim 1730218887Sdim/// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object 1731218887Sdim/// and collapses PathDiagosticPieces that are expanded by macros. 1732234353Sdimstatic void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) { 1733234353Sdim typedef std::vector<std::pair<IntrusiveRefCntPtr<PathDiagnosticMacroPiece>, 1734234353Sdim SourceLocation> > MacroStackTy; 1735218887Sdim 1736234353Sdim typedef std::vector<IntrusiveRefCntPtr<PathDiagnosticPiece> > 1737218887Sdim PiecesTy; 1738218887Sdim 1739218887Sdim MacroStackTy MacroStack; 1740218887Sdim PiecesTy Pieces; 1741218887Sdim 1742234353Sdim for (PathPieces::const_iterator I = path.begin(), E = path.end(); 1743234353Sdim I!=E; ++I) { 1744234353Sdim 1745234353Sdim PathDiagnosticPiece *piece = I->getPtr(); 1746234353Sdim 1747234353Sdim // Recursively compact calls. 1748234353Sdim if (PathDiagnosticCallPiece *call=dyn_cast<PathDiagnosticCallPiece>(piece)){ 1749234353Sdim CompactPathDiagnostic(call->path, SM); 1750234353Sdim } 1751234353Sdim 1752218887Sdim // Get the location of the PathDiagnosticPiece. 1753234353Sdim const FullSourceLoc Loc = piece->getLocation().asLocation(); 1754218887Sdim 1755218887Sdim // Determine the instantiation location, which is the location we group 1756218887Sdim // related PathDiagnosticPieces. 1757218887Sdim SourceLocation InstantiationLoc = Loc.isMacroID() ? 1758226633Sdim SM.getExpansionLoc(Loc) : 1759218887Sdim SourceLocation(); 1760218887Sdim 1761218887Sdim if (Loc.isFileID()) { 1762218887Sdim MacroStack.clear(); 1763234353Sdim Pieces.push_back(piece); 1764218887Sdim continue; 1765218887Sdim } 1766218887Sdim 1767218887Sdim assert(Loc.isMacroID()); 1768218887Sdim 1769218887Sdim // Is the PathDiagnosticPiece within the same macro group? 1770218887Sdim if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) { 1771234353Sdim MacroStack.back().first->subPieces.push_back(piece); 1772218887Sdim continue; 1773218887Sdim } 1774218887Sdim 1775218887Sdim // We aren't in the same group. Are we descending into a new macro 1776218887Sdim // or are part of an old one? 1777234353Sdim IntrusiveRefCntPtr<PathDiagnosticMacroPiece> MacroGroup; 1778218887Sdim 1779218887Sdim SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ? 1780226633Sdim SM.getExpansionLoc(Loc) : 1781218887Sdim SourceLocation(); 1782218887Sdim 1783218887Sdim // Walk the entire macro stack. 1784218887Sdim while (!MacroStack.empty()) { 1785218887Sdim if (InstantiationLoc == MacroStack.back().second) { 1786218887Sdim MacroGroup = MacroStack.back().first; 1787218887Sdim break; 1788218887Sdim } 1789218887Sdim 1790218887Sdim if (ParentInstantiationLoc == MacroStack.back().second) { 1791218887Sdim MacroGroup = MacroStack.back().first; 1792218887Sdim break; 1793218887Sdim } 1794218887Sdim 1795218887Sdim MacroStack.pop_back(); 1796218887Sdim } 1797218887Sdim 1798218887Sdim if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) { 1799218887Sdim // Create a new macro group and add it to the stack. 1800226633Sdim PathDiagnosticMacroPiece *NewGroup = 1801226633Sdim new PathDiagnosticMacroPiece( 1802234353Sdim PathDiagnosticLocation::createSingleLocation(piece->getLocation())); 1803218887Sdim 1804218887Sdim if (MacroGroup) 1805234353Sdim MacroGroup->subPieces.push_back(NewGroup); 1806218887Sdim else { 1807218887Sdim assert(InstantiationLoc.isFileID()); 1808218887Sdim Pieces.push_back(NewGroup); 1809218887Sdim } 1810218887Sdim 1811218887Sdim MacroGroup = NewGroup; 1812218887Sdim MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc)); 1813218887Sdim } 1814218887Sdim 1815218887Sdim // Finally, add the PathDiagnosticPiece to the group. 1816234353Sdim MacroGroup->subPieces.push_back(piece); 1817218887Sdim } 1818218887Sdim 1819218887Sdim // Now take the pieces and construct a new PathDiagnostic. 1820234353Sdim path.clear(); 1821218887Sdim 1822234353Sdim for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I) 1823234353Sdim path.push_back(*I); 1824218887Sdim} 1825218887Sdim 1826218887Sdimvoid GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, 1827239462Sdim PathDiagnosticConsumer &PC, 1828239462Sdim ArrayRef<BugReport *> &bugReports) { 1829218887Sdim 1830218887Sdim assert(!bugReports.empty()); 1831226633Sdim SmallVector<const ExplodedNode *, 10> errorNodes; 1832239462Sdim for (ArrayRef<BugReport*>::iterator I = bugReports.begin(), 1833239462Sdim E = bugReports.end(); I != E; ++I) { 1834218887Sdim errorNodes.push_back((*I)->getErrorNode()); 1835218887Sdim } 1836218887Sdim 1837218887Sdim // Construct a new graph that contains only a single path from the error 1838218887Sdim // node to a root. 1839218887Sdim const std::pair<std::pair<ExplodedGraph*, NodeBackMap*>, 1840218887Sdim std::pair<ExplodedNode*, unsigned> >& 1841218887Sdim GPair = MakeReportGraph(&getGraph(), errorNodes); 1842218887Sdim 1843218887Sdim // Find the BugReport with the original location. 1844218887Sdim assert(GPair.second.second < bugReports.size()); 1845218887Sdim BugReport *R = bugReports[GPair.second.second]; 1846218887Sdim assert(R && "No original report found for sliced graph."); 1847218887Sdim 1848234353Sdim OwningPtr<ExplodedGraph> ReportGraph(GPair.first.first); 1849234353Sdim OwningPtr<NodeBackMap> BackMap(GPair.first.second); 1850218887Sdim const ExplodedNode *N = GPair.second.first; 1851218887Sdim 1852218887Sdim // Start building the path diagnostic... 1853239462Sdim PathDiagnosticBuilder PDB(*this, R, BackMap.get(), &PC); 1854218887Sdim 1855226633Sdim // Register additional node visitors. 1856226633Sdim R->addVisitor(new NilReceiverBRVisitor()); 1857226633Sdim R->addVisitor(new ConditionBRVisitor()); 1858226633Sdim 1859234353Sdim BugReport::VisitorList visitors; 1860234353Sdim unsigned originalReportConfigToken, finalReportConfigToken; 1861234353Sdim 1862234353Sdim // While generating diagnostics, it's possible the visitors will decide 1863234353Sdim // new symbols and regions are interesting, or add other visitors based on 1864234353Sdim // the information they find. If they do, we need to regenerate the path 1865234353Sdim // based on our new report configuration. 1866234353Sdim do { 1867234353Sdim // Get a clean copy of all the visitors. 1868234353Sdim for (BugReport::visitor_iterator I = R->visitor_begin(), 1869234353Sdim E = R->visitor_end(); I != E; ++I) 1870234353Sdim visitors.push_back((*I)->clone()); 1871234353Sdim 1872234353Sdim // Clear out the active path from any previous work. 1873234353Sdim PD.getActivePath().clear(); 1874234353Sdim originalReportConfigToken = R->getConfigurationChangeToken(); 1875234353Sdim 1876234353Sdim // Generate the very last diagnostic piece - the piece is visible before 1877234353Sdim // the trace is expanded. 1878234353Sdim PathDiagnosticPiece *LastPiece = 0; 1879234353Sdim for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end(); 1880234353Sdim I != E; ++I) { 1881234353Sdim if (PathDiagnosticPiece *Piece = (*I)->getEndPath(PDB, N, *R)) { 1882234353Sdim assert (!LastPiece && 1883234353Sdim "There can only be one final piece in a diagnostic."); 1884234353Sdim LastPiece = Piece; 1885234353Sdim } 1886226633Sdim } 1887234353Sdim if (!LastPiece) 1888234353Sdim LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R); 1889234353Sdim if (LastPiece) 1890234353Sdim PD.getActivePath().push_back(LastPiece); 1891234353Sdim else 1892234353Sdim return; 1893218887Sdim 1894234353Sdim switch (PDB.getGenerationScheme()) { 1895226633Sdim case PathDiagnosticConsumer::Extensive: 1896234353Sdim GenerateExtensivePathDiagnostic(PD, PDB, N, visitors); 1897218887Sdim break; 1898226633Sdim case PathDiagnosticConsumer::Minimal: 1899234353Sdim GenerateMinimalPathDiagnostic(PD, PDB, N, visitors); 1900218887Sdim break; 1901239462Sdim case PathDiagnosticConsumer::None: 1902239462Sdim llvm_unreachable("PathDiagnosticConsumer::None should never appear here"); 1903234353Sdim } 1904234353Sdim 1905234353Sdim // Clean up the visitors we used. 1906234353Sdim llvm::DeleteContainerPointers(visitors); 1907234353Sdim 1908234353Sdim // Did anything change while generating this path? 1909234353Sdim finalReportConfigToken = R->getConfigurationChangeToken(); 1910234353Sdim } while(finalReportConfigToken != originalReportConfigToken); 1911234353Sdim 1912234353Sdim // Finally, prune the diagnostic path of uninteresting stuff. 1913239462Sdim if (R->shouldPrunePath()) { 1914239462Sdim bool hasSomethingInteresting = RemoveUneededCalls(PD.getMutablePieces()); 1915239462Sdim assert(hasSomethingInteresting); 1916239462Sdim (void) hasSomethingInteresting; 1917239462Sdim } 1918218887Sdim} 1919218887Sdim 1920218887Sdimvoid BugReporter::Register(BugType *BT) { 1921218887Sdim BugTypes = F.add(BugTypes, BT); 1922218887Sdim} 1923218887Sdim 1924218887Sdimvoid BugReporter::EmitReport(BugReport* R) { 1925218887Sdim // Compute the bug report's hash to determine its equivalence class. 1926218887Sdim llvm::FoldingSetNodeID ID; 1927218887Sdim R->Profile(ID); 1928218887Sdim 1929218887Sdim // Lookup the equivance class. If there isn't one, create it. 1930218887Sdim BugType& BT = R->getBugType(); 1931218887Sdim Register(&BT); 1932218887Sdim void *InsertPos; 1933219077Sdim BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos); 1934218887Sdim 1935218887Sdim if (!EQ) { 1936218887Sdim EQ = new BugReportEquivClass(R); 1937219077Sdim EQClasses.InsertNode(EQ, InsertPos); 1938226633Sdim EQClassesVector.push_back(EQ); 1939218887Sdim } 1940218887Sdim else 1941218887Sdim EQ->AddReport(R); 1942218887Sdim} 1943218887Sdim 1944218887Sdim 1945218887Sdim//===----------------------------------------------------------------------===// 1946218887Sdim// Emitting reports in equivalence classes. 1947218887Sdim//===----------------------------------------------------------------------===// 1948218887Sdim 1949218887Sdimnamespace { 1950218887Sdimstruct FRIEC_WLItem { 1951218887Sdim const ExplodedNode *N; 1952218887Sdim ExplodedNode::const_succ_iterator I, E; 1953218887Sdim 1954218887Sdim FRIEC_WLItem(const ExplodedNode *n) 1955218887Sdim : N(n), I(N->succ_begin()), E(N->succ_end()) {} 1956218887Sdim}; 1957218887Sdim} 1958218887Sdim 1959218887Sdimstatic BugReport * 1960218887SdimFindReportInEquivalenceClass(BugReportEquivClass& EQ, 1961226633Sdim SmallVectorImpl<BugReport*> &bugReports) { 1962218887Sdim 1963218887Sdim BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end(); 1964218887Sdim assert(I != E); 1965234353Sdim BugType& BT = I->getBugType(); 1966218887Sdim 1967218887Sdim // If we don't need to suppress any of the nodes because they are 1968218887Sdim // post-dominated by a sink, simply add all the nodes in the equivalence class 1969218887Sdim // to 'Nodes'. Any of the reports will serve as a "representative" report. 1970218887Sdim if (!BT.isSuppressOnSink()) { 1971234353Sdim BugReport *R = I; 1972218887Sdim for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) { 1973226633Sdim const ExplodedNode *N = I->getErrorNode(); 1974218887Sdim if (N) { 1975234353Sdim R = I; 1976218887Sdim bugReports.push_back(R); 1977218887Sdim } 1978218887Sdim } 1979218887Sdim return R; 1980218887Sdim } 1981218887Sdim 1982218887Sdim // For bug reports that should be suppressed when all paths are post-dominated 1983218887Sdim // by a sink node, iterate through the reports in the equivalence class 1984218887Sdim // until we find one that isn't post-dominated (if one exists). We use a 1985218887Sdim // DFS traversal of the ExplodedGraph to find a non-sink node. We could write 1986218887Sdim // this as a recursive function, but we don't want to risk blowing out the 1987218887Sdim // stack for very long paths. 1988218887Sdim BugReport *exampleReport = 0; 1989218887Sdim 1990218887Sdim for (; I != E; ++I) { 1991234353Sdim const ExplodedNode *errorNode = I->getErrorNode(); 1992218887Sdim 1993218887Sdim if (!errorNode) 1994218887Sdim continue; 1995218887Sdim if (errorNode->isSink()) { 1996226633Sdim llvm_unreachable( 1997218887Sdim "BugType::isSuppressSink() should not be 'true' for sink end nodes"); 1998218887Sdim } 1999218887Sdim // No successors? By definition this nodes isn't post-dominated by a sink. 2000218887Sdim if (errorNode->succ_empty()) { 2001234353Sdim bugReports.push_back(I); 2002218887Sdim if (!exampleReport) 2003234353Sdim exampleReport = I; 2004218887Sdim continue; 2005218887Sdim } 2006218887Sdim 2007218887Sdim // At this point we know that 'N' is not a sink and it has at least one 2008218887Sdim // successor. Use a DFS worklist to find a non-sink end-of-path node. 2009218887Sdim typedef FRIEC_WLItem WLItem; 2010226633Sdim typedef SmallVector<WLItem, 10> DFSWorkList; 2011218887Sdim llvm::DenseMap<const ExplodedNode *, unsigned> Visited; 2012218887Sdim 2013218887Sdim DFSWorkList WL; 2014218887Sdim WL.push_back(errorNode); 2015218887Sdim Visited[errorNode] = 1; 2016218887Sdim 2017218887Sdim while (!WL.empty()) { 2018218887Sdim WLItem &WI = WL.back(); 2019218887Sdim assert(!WI.N->succ_empty()); 2020218887Sdim 2021218887Sdim for (; WI.I != WI.E; ++WI.I) { 2022218887Sdim const ExplodedNode *Succ = *WI.I; 2023218887Sdim // End-of-path node? 2024218887Sdim if (Succ->succ_empty()) { 2025218887Sdim // If we found an end-of-path node that is not a sink. 2026218887Sdim if (!Succ->isSink()) { 2027234353Sdim bugReports.push_back(I); 2028218887Sdim if (!exampleReport) 2029234353Sdim exampleReport = I; 2030218887Sdim WL.clear(); 2031218887Sdim break; 2032218887Sdim } 2033218887Sdim // Found a sink? Continue on to the next successor. 2034218887Sdim continue; 2035218887Sdim } 2036218887Sdim // Mark the successor as visited. If it hasn't been explored, 2037218887Sdim // enqueue it to the DFS worklist. 2038218887Sdim unsigned &mark = Visited[Succ]; 2039218887Sdim if (!mark) { 2040218887Sdim mark = 1; 2041218887Sdim WL.push_back(Succ); 2042218887Sdim break; 2043218887Sdim } 2044218887Sdim } 2045218887Sdim 2046218887Sdim // The worklist may have been cleared at this point. First 2047218887Sdim // check if it is empty before checking the last item. 2048218887Sdim if (!WL.empty() && &WL.back() == &WI) 2049218887Sdim WL.pop_back(); 2050218887Sdim } 2051218887Sdim } 2052218887Sdim 2053218887Sdim // ExampleReport will be NULL if all the nodes in the equivalence class 2054218887Sdim // were post-dominated by sinks. 2055218887Sdim return exampleReport; 2056218887Sdim} 2057218887Sdim 2058239462Sdimvoid BugReporter::FlushReport(BugReportEquivClass& EQ) { 2059239462Sdim SmallVector<BugReport*, 10> bugReports; 2060239462Sdim BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports); 2061239462Sdim if (exampleReport) { 2062239462Sdim const PathDiagnosticConsumers &C = getPathDiagnosticConsumers(); 2063239462Sdim for (PathDiagnosticConsumers::const_iterator I=C.begin(), 2064239462Sdim E=C.end(); I != E; ++I) { 2065239462Sdim FlushReport(exampleReport, **I, bugReports); 2066239462Sdim } 2067218887Sdim } 2068218887Sdim} 2069218887Sdim 2070239462Sdimvoid BugReporter::FlushReport(BugReport *exampleReport, 2071239462Sdim PathDiagnosticConsumer &PD, 2072239462Sdim ArrayRef<BugReport*> bugReports) { 2073218887Sdim 2074218887Sdim // FIXME: Make sure we use the 'R' for the path that was actually used. 2075218887Sdim // Probably doesn't make a difference in practice. 2076218887Sdim BugType& BT = exampleReport->getBugType(); 2077218887Sdim 2078234353Sdim OwningPtr<PathDiagnostic> 2079234353Sdim D(new PathDiagnostic(exampleReport->getDeclWithIssue(), 2080234353Sdim exampleReport->getBugType().getName(), 2081239462Sdim PD.useVerboseDescription() 2082218887Sdim ? exampleReport->getDescription() 2083218887Sdim : exampleReport->getShortDescription(), 2084218887Sdim BT.getCategory())); 2085218887Sdim 2086239462Sdim // Generate the full path diagnostic, using the generation scheme 2087239462Sdim // specified by the PathDiagnosticConsumer. 2088239462Sdim if (PD.getGenerationScheme() != PathDiagnosticConsumer::None) { 2089239462Sdim if (!bugReports.empty()) 2090239462Sdim GeneratePathDiagnostic(*D.get(), PD, bugReports); 2091226633Sdim } 2092218887Sdim 2093239462Sdim // If the path is empty, generate a single step path with the location 2094239462Sdim // of the issue. 2095234353Sdim if (D->path.empty()) { 2096239462Sdim PathDiagnosticLocation L = exampleReport->getLocation(getSourceManager()); 2097239462Sdim PathDiagnosticPiece *piece = 2098239462Sdim new PathDiagnosticEventPiece(L, exampleReport->getDescription()); 2099239462Sdim BugReport::ranges_iterator Beg, End; 2100239462Sdim llvm::tie(Beg, End) = exampleReport->getRanges(); 2101234353Sdim for ( ; Beg != End; ++Beg) 2102234353Sdim piece->addRange(*Beg); 2103234353Sdim D->getActivePath().push_back(piece); 2104218887Sdim } 2105218887Sdim 2106239462Sdim // Get the meta data. 2107239462Sdim const BugReport::ExtraTextList &Meta = exampleReport->getExtraText(); 2108239462Sdim for (BugReport::ExtraTextList::const_iterator i = Meta.begin(), 2109239462Sdim e = Meta.end(); i != e; ++i) { 2110239462Sdim D->addMeta(*i); 2111239462Sdim } 2112239462Sdim 2113239462Sdim PD.HandlePathDiagnostic(D.take()); 2114218887Sdim} 2115218887Sdim 2116234353Sdimvoid BugReporter::EmitBasicReport(const Decl *DeclWithIssue, 2117234353Sdim StringRef name, 2118226633Sdim StringRef category, 2119226633Sdim StringRef str, PathDiagnosticLocation Loc, 2120218887Sdim SourceRange* RBeg, unsigned NumRanges) { 2121218887Sdim 2122219077Sdim // 'BT' is owned by BugReporter. 2123219077Sdim BugType *BT = getBugTypeForName(name, category); 2124226633Sdim BugReport *R = new BugReport(*BT, str, Loc); 2125234353Sdim R->setDeclWithIssue(DeclWithIssue); 2126218887Sdim for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg); 2127218887Sdim EmitReport(R); 2128218887Sdim} 2129219077Sdim 2130226633SdimBugType *BugReporter::getBugTypeForName(StringRef name, 2131226633Sdim StringRef category) { 2132234353Sdim SmallString<136> fullDesc; 2133219077Sdim llvm::raw_svector_ostream(fullDesc) << name << ":" << category; 2134219077Sdim llvm::StringMapEntry<BugType *> & 2135219077Sdim entry = StrBugTypes.GetOrCreateValue(fullDesc); 2136219077Sdim BugType *BT = entry.getValue(); 2137219077Sdim if (!BT) { 2138219077Sdim BT = new BugType(name, category); 2139219077Sdim entry.setValue(BT); 2140219077Sdim } 2141219077Sdim return BT; 2142219077Sdim} 2143