BugReporter.cpp revision b85cce094887ab5cf1c47acfe306e2fb1d3cfbb1
1// BugReporter.cpp - Generate PathDiagnostics for Bugs ------------*- C++ -*--// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines BugReporter, a utility class for generating 11// PathDiagnostics. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 16#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 17#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 18#include "clang/AST/ASTContext.h" 19#include "clang/Analysis/CFG.h" 20#include "clang/AST/DeclObjC.h" 21#include "clang/AST/Expr.h" 22#include "clang/AST/ParentMap.h" 23#include "clang/AST/StmtObjC.h" 24#include "clang/Basic/SourceManager.h" 25#include "clang/Analysis/ProgramPoint.h" 26#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" 27#include "llvm/Support/raw_ostream.h" 28#include "llvm/ADT/DenseMap.h" 29#include "llvm/ADT/SmallString.h" 30#include "llvm/ADT/STLExtras.h" 31#include "llvm/ADT/OwningPtr.h" 32#include "llvm/ADT/IntrusiveRefCntPtr.h" 33#include <queue> 34 35using namespace clang; 36using namespace ento; 37 38BugReporterVisitor::~BugReporterVisitor() {} 39 40void BugReporterContext::anchor() {} 41 42//===----------------------------------------------------------------------===// 43// Helper routines for walking the ExplodedGraph and fetching statements. 44//===----------------------------------------------------------------------===// 45 46static inline const Stmt *GetStmt(const ProgramPoint &P) { 47 if (const StmtPoint* SP = dyn_cast<StmtPoint>(&P)) 48 return SP->getStmt(); 49 else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) 50 return BE->getSrc()->getTerminator(); 51 else if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) 52 return CE->getCallExpr(); 53 else if (const CallExitEnd *CEE = dyn_cast<CallExitEnd>(&P)) 54 return CEE->getCalleeContext()->getCallSite(); 55 56 return 0; 57} 58 59static inline const ExplodedNode* 60GetPredecessorNode(const ExplodedNode *N) { 61 return N->pred_empty() ? NULL : *(N->pred_begin()); 62} 63 64static inline const ExplodedNode* 65GetSuccessorNode(const ExplodedNode *N) { 66 return N->succ_empty() ? NULL : *(N->succ_begin()); 67} 68 69static const Stmt *GetPreviousStmt(const ExplodedNode *N) { 70 for (N = GetPredecessorNode(N); N; N = GetPredecessorNode(N)) 71 if (const Stmt *S = GetStmt(N->getLocation())) 72 return S; 73 74 return 0; 75} 76 77static const Stmt *GetNextStmt(const ExplodedNode *N) { 78 for (N = GetSuccessorNode(N); N; N = GetSuccessorNode(N)) 79 if (const Stmt *S = GetStmt(N->getLocation())) { 80 // Check if the statement is '?' or '&&'/'||'. These are "merges", 81 // not actual statement points. 82 switch (S->getStmtClass()) { 83 case Stmt::ChooseExprClass: 84 case Stmt::BinaryConditionalOperatorClass: continue; 85 case Stmt::ConditionalOperatorClass: continue; 86 case Stmt::BinaryOperatorClass: { 87 BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode(); 88 if (Op == BO_LAnd || Op == BO_LOr) 89 continue; 90 break; 91 } 92 default: 93 break; 94 } 95 return S; 96 } 97 98 return 0; 99} 100 101static inline const Stmt* 102GetCurrentOrPreviousStmt(const ExplodedNode *N) { 103 if (const Stmt *S = GetStmt(N->getLocation())) 104 return S; 105 106 return GetPreviousStmt(N); 107} 108 109static inline const Stmt* 110GetCurrentOrNextStmt(const ExplodedNode *N) { 111 if (const Stmt *S = GetStmt(N->getLocation())) 112 return S; 113 114 return GetNextStmt(N); 115} 116 117//===----------------------------------------------------------------------===// 118// Diagnostic cleanup. 119//===----------------------------------------------------------------------===// 120 121static PathDiagnosticEventPiece * 122eventsDescribeSameCondition(PathDiagnosticEventPiece *X, 123 PathDiagnosticEventPiece *Y) { 124 // Prefer diagnostics that come from ConditionBRVisitor over 125 // those that came from TrackConstraintBRVisitor. 126 const void *tagPreferred = ConditionBRVisitor::getTag(); 127 const void *tagLesser = TrackConstraintBRVisitor::getTag(); 128 129 if (X->getLocation() != Y->getLocation()) 130 return 0; 131 132 if (X->getTag() == tagPreferred && Y->getTag() == tagLesser) 133 return X; 134 135 if (Y->getTag() == tagPreferred && X->getTag() == tagLesser) 136 return Y; 137 138 return 0; 139} 140 141static void RemoveRedundantMsgs(PathPieces &path) { 142 unsigned N = path.size(); 143 if (N < 2) 144 return; 145 for (unsigned i = 0; i < N; ++i) { 146 IntrusiveRefCntPtr<PathDiagnosticPiece> piece(path.front()); 147 path.pop_front(); 148 149 switch (piece->getKind()) { 150 case clang::ento::PathDiagnosticPiece::Call: 151 RemoveRedundantMsgs(cast<PathDiagnosticCallPiece>(piece)->path); 152 break; 153 case clang::ento::PathDiagnosticPiece::Macro: 154 RemoveRedundantMsgs(cast<PathDiagnosticMacroPiece>(piece)->subPieces); 155 break; 156 case clang::ento::PathDiagnosticPiece::ControlFlow: 157 break; 158 case clang::ento::PathDiagnosticPiece::Event: { 159 if (i == N-1) 160 break; 161 162 if (PathDiagnosticEventPiece *nextEvent = 163 dyn_cast<PathDiagnosticEventPiece>(path.front().getPtr())) { 164 PathDiagnosticEventPiece *event = 165 cast<PathDiagnosticEventPiece>(piece); 166 // Check to see if we should keep one of the two pieces. If we 167 // come up with a preference, record which piece to keep, and consume 168 // another piece from the path. 169 if (PathDiagnosticEventPiece *pieceToKeep = 170 eventsDescribeSameCondition(event, nextEvent)) { 171 piece = pieceToKeep; 172 path.pop_front(); 173 ++i; 174 } 175 } 176 break; 177 } 178 } 179 path.push_back(piece); 180 } 181} 182 183/// Recursively scan through a path and prune out calls and macros pieces 184/// that aren't needed. Return true if afterwards the path contains 185/// "interesting stuff" which means it should be pruned from the parent path. 186bool BugReporter::RemoveUneededCalls(PathPieces &pieces, BugReport *R, 187 PathDiagnosticCallPiece *CallWithLoc) { 188 bool containsSomethingInteresting = false; 189 const unsigned N = pieces.size(); 190 191 for (unsigned i = 0 ; i < N ; ++i) { 192 // Remove the front piece from the path. If it is still something we 193 // want to keep once we are done, we will push it back on the end. 194 IntrusiveRefCntPtr<PathDiagnosticPiece> piece(pieces.front()); 195 pieces.pop_front(); 196 197 // Throw away pieces with invalid locations. 198 if (piece->getKind() != PathDiagnosticPiece::Call && 199 piece->getLocation().asLocation().isInvalid()) 200 continue; 201 202 switch (piece->getKind()) { 203 case PathDiagnosticPiece::Call: { 204 PathDiagnosticCallPiece *call = cast<PathDiagnosticCallPiece>(piece); 205 // Check if the location context is interesting. 206 assert(LocationContextMap.count(call)); 207 if (R->isInteresting(LocationContextMap[call])) { 208 containsSomethingInteresting = true; 209 break; 210 } 211 // Recursively clean out the subclass. Keep this call around if 212 // it contains any informative diagnostics. 213 PathDiagnosticCallPiece *NewCallWithLoc = 214 call->getLocation().asLocation().isValid() 215 ? call : CallWithLoc; 216 217 if (!RemoveUneededCalls(call->path, R, NewCallWithLoc)) 218 continue; 219 220 if (NewCallWithLoc == CallWithLoc && CallWithLoc) { 221 call->callEnter = CallWithLoc->callEnter; 222 } 223 224 containsSomethingInteresting = true; 225 break; 226 } 227 case PathDiagnosticPiece::Macro: { 228 PathDiagnosticMacroPiece *macro = cast<PathDiagnosticMacroPiece>(piece); 229 if (!RemoveUneededCalls(macro->subPieces, R)) 230 continue; 231 containsSomethingInteresting = true; 232 break; 233 } 234 case PathDiagnosticPiece::Event: { 235 PathDiagnosticEventPiece *event = cast<PathDiagnosticEventPiece>(piece); 236 237 // We never throw away an event, but we do throw it away wholesale 238 // as part of a path if we throw the entire path away. 239 containsSomethingInteresting |= !event->isPrunable(); 240 break; 241 } 242 case PathDiagnosticPiece::ControlFlow: 243 break; 244 } 245 246 pieces.push_back(piece); 247 } 248 249 return containsSomethingInteresting; 250} 251 252//===----------------------------------------------------------------------===// 253// PathDiagnosticBuilder and its associated routines and helper objects. 254//===----------------------------------------------------------------------===// 255 256typedef llvm::DenseMap<const ExplodedNode*, 257const ExplodedNode*> NodeBackMap; 258 259namespace { 260class NodeMapClosure : public BugReport::NodeResolver { 261 NodeBackMap& M; 262public: 263 NodeMapClosure(NodeBackMap *m) : M(*m) {} 264 ~NodeMapClosure() {} 265 266 const ExplodedNode *getOriginalNode(const ExplodedNode *N) { 267 NodeBackMap::iterator I = M.find(N); 268 return I == M.end() ? 0 : I->second; 269 } 270}; 271 272class PathDiagnosticBuilder : public BugReporterContext { 273 BugReport *R; 274 PathDiagnosticConsumer *PDC; 275 OwningPtr<ParentMap> PM; 276 NodeMapClosure NMC; 277public: 278 const LocationContext *LC; 279 280 PathDiagnosticBuilder(GRBugReporter &br, 281 BugReport *r, NodeBackMap *Backmap, 282 PathDiagnosticConsumer *pdc) 283 : BugReporterContext(br), 284 R(r), PDC(pdc), NMC(Backmap), LC(r->getErrorNode()->getLocationContext()) 285 {} 286 287 PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N); 288 289 PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os, 290 const ExplodedNode *N); 291 292 BugReport *getBugReport() { return R; } 293 294 Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); } 295 296 ParentMap& getParentMap() { return LC->getParentMap(); } 297 298 const Stmt *getParent(const Stmt *S) { 299 return getParentMap().getParent(S); 300 } 301 302 virtual NodeMapClosure& getNodeResolver() { return NMC; } 303 304 PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S); 305 306 PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const { 307 return PDC ? PDC->getGenerationScheme() : PathDiagnosticConsumer::Extensive; 308 } 309 310 bool supportsLogicalOpControlFlow() const { 311 return PDC ? PDC->supportsLogicalOpControlFlow() : true; 312 } 313}; 314} // end anonymous namespace 315 316PathDiagnosticLocation 317PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) { 318 if (const Stmt *S = GetNextStmt(N)) 319 return PathDiagnosticLocation(S, getSourceManager(), LC); 320 321 return PathDiagnosticLocation::createDeclEnd(N->getLocationContext(), 322 getSourceManager()); 323} 324 325PathDiagnosticLocation 326PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os, 327 const ExplodedNode *N) { 328 329 // Slow, but probably doesn't matter. 330 if (os.str().empty()) 331 os << ' '; 332 333 const PathDiagnosticLocation &Loc = ExecutionContinues(N); 334 335 if (Loc.asStmt()) 336 os << "Execution continues on line " 337 << getSourceManager().getExpansionLineNumber(Loc.asLocation()) 338 << '.'; 339 else { 340 os << "Execution jumps to the end of the "; 341 const Decl *D = N->getLocationContext()->getDecl(); 342 if (isa<ObjCMethodDecl>(D)) 343 os << "method"; 344 else if (isa<FunctionDecl>(D)) 345 os << "function"; 346 else { 347 assert(isa<BlockDecl>(D)); 348 os << "anonymous block"; 349 } 350 os << '.'; 351 } 352 353 return Loc; 354} 355 356static bool IsNested(const Stmt *S, ParentMap &PM) { 357 if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S))) 358 return true; 359 360 const Stmt *Parent = PM.getParentIgnoreParens(S); 361 362 if (Parent) 363 switch (Parent->getStmtClass()) { 364 case Stmt::ForStmtClass: 365 case Stmt::DoStmtClass: 366 case Stmt::WhileStmtClass: 367 return true; 368 default: 369 break; 370 } 371 372 return false; 373} 374 375PathDiagnosticLocation 376PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { 377 assert(S && "Null Stmt *passed to getEnclosingStmtLocation"); 378 ParentMap &P = getParentMap(); 379 SourceManager &SMgr = getSourceManager(); 380 381 while (IsNested(S, P)) { 382 const Stmt *Parent = P.getParentIgnoreParens(S); 383 384 if (!Parent) 385 break; 386 387 switch (Parent->getStmtClass()) { 388 case Stmt::BinaryOperatorClass: { 389 const BinaryOperator *B = cast<BinaryOperator>(Parent); 390 if (B->isLogicalOp()) 391 return PathDiagnosticLocation(S, SMgr, LC); 392 break; 393 } 394 case Stmt::CompoundStmtClass: 395 case Stmt::StmtExprClass: 396 return PathDiagnosticLocation(S, SMgr, LC); 397 case Stmt::ChooseExprClass: 398 // Similar to '?' if we are referring to condition, just have the edge 399 // point to the entire choose expression. 400 if (cast<ChooseExpr>(Parent)->getCond() == S) 401 return PathDiagnosticLocation(Parent, SMgr, LC); 402 else 403 return PathDiagnosticLocation(S, SMgr, LC); 404 case Stmt::BinaryConditionalOperatorClass: 405 case Stmt::ConditionalOperatorClass: 406 // For '?', if we are referring to condition, just have the edge point 407 // to the entire '?' expression. 408 if (cast<AbstractConditionalOperator>(Parent)->getCond() == S) 409 return PathDiagnosticLocation(Parent, SMgr, LC); 410 else 411 return PathDiagnosticLocation(S, SMgr, LC); 412 case Stmt::DoStmtClass: 413 return PathDiagnosticLocation(S, SMgr, LC); 414 case Stmt::ForStmtClass: 415 if (cast<ForStmt>(Parent)->getBody() == S) 416 return PathDiagnosticLocation(S, SMgr, LC); 417 break; 418 case Stmt::IfStmtClass: 419 if (cast<IfStmt>(Parent)->getCond() != S) 420 return PathDiagnosticLocation(S, SMgr, LC); 421 break; 422 case Stmt::ObjCForCollectionStmtClass: 423 if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S) 424 return PathDiagnosticLocation(S, SMgr, LC); 425 break; 426 case Stmt::WhileStmtClass: 427 if (cast<WhileStmt>(Parent)->getCond() != S) 428 return PathDiagnosticLocation(S, SMgr, LC); 429 break; 430 default: 431 break; 432 } 433 434 S = Parent; 435 } 436 437 assert(S && "Cannot have null Stmt for PathDiagnosticLocation"); 438 439 // Special case: DeclStmts can appear in for statement declarations, in which 440 // case the ForStmt is the context. 441 if (isa<DeclStmt>(S)) { 442 if (const Stmt *Parent = P.getParent(S)) { 443 switch (Parent->getStmtClass()) { 444 case Stmt::ForStmtClass: 445 case Stmt::ObjCForCollectionStmtClass: 446 return PathDiagnosticLocation(Parent, SMgr, LC); 447 default: 448 break; 449 } 450 } 451 } 452 else if (isa<BinaryOperator>(S)) { 453 // Special case: the binary operator represents the initialization 454 // code in a for statement (this can happen when the variable being 455 // initialized is an old variable. 456 if (const ForStmt *FS = 457 dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) { 458 if (FS->getInit() == S) 459 return PathDiagnosticLocation(FS, SMgr, LC); 460 } 461 } 462 463 return PathDiagnosticLocation(S, SMgr, LC); 464} 465 466//===----------------------------------------------------------------------===// 467// "Visitors only" path diagnostic generation algorithm. 468//===----------------------------------------------------------------------===// 469static bool GenerateVisitorsOnlyPathDiagnostic(PathDiagnostic &PD, 470 PathDiagnosticBuilder &PDB, 471 const ExplodedNode *N, 472 ArrayRef<BugReporterVisitor *> visitors) { 473 // All path generation skips the very first node (the error node). 474 // This is because there is special handling for the end-of-path note. 475 N = N->getFirstPred(); 476 if (!N) 477 return true; 478 479 BugReport *R = PDB.getBugReport(); 480 while (const ExplodedNode *Pred = N->getFirstPred()) { 481 for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(), 482 E = visitors.end(); 483 I != E; ++I) { 484 // Visit all the node pairs, but throw the path pieces away. 485 PathDiagnosticPiece *Piece = (*I)->VisitNode(N, Pred, PDB, *R); 486 delete Piece; 487 } 488 489 N = Pred; 490 } 491 492 return R->isValid(); 493} 494 495//===----------------------------------------------------------------------===// 496// "Minimal" path diagnostic generation algorithm. 497//===----------------------------------------------------------------------===// 498typedef std::pair<PathDiagnosticCallPiece*, const ExplodedNode*> StackDiagPair; 499typedef SmallVector<StackDiagPair, 6> StackDiagVector; 500 501static void updateStackPiecesWithMessage(PathDiagnosticPiece *P, 502 StackDiagVector &CallStack) { 503 // If the piece contains a special message, add it to all the call 504 // pieces on the active stack. 505 if (PathDiagnosticEventPiece *ep = 506 dyn_cast<PathDiagnosticEventPiece>(P)) { 507 508 if (ep->hasCallStackHint()) 509 for (StackDiagVector::iterator I = CallStack.begin(), 510 E = CallStack.end(); I != E; ++I) { 511 PathDiagnosticCallPiece *CP = I->first; 512 const ExplodedNode *N = I->second; 513 std::string stackMsg = ep->getCallStackMessage(N); 514 515 // The last message on the path to final bug is the most important 516 // one. Since we traverse the path backwards, do not add the message 517 // if one has been previously added. 518 if (!CP->hasCallStackMessage()) 519 CP->setCallStackMessage(stackMsg); 520 } 521 } 522} 523 524static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM); 525 526static bool GenerateMinimalPathDiagnostic(PathDiagnostic& PD, 527 PathDiagnosticBuilder &PDB, 528 const ExplodedNode *N, 529 ArrayRef<BugReporterVisitor *> visitors) { 530 531 SourceManager& SMgr = PDB.getSourceManager(); 532 const LocationContext *LC = PDB.LC; 533 const ExplodedNode *NextNode = N->pred_empty() 534 ? NULL : *(N->pred_begin()); 535 536 StackDiagVector CallStack; 537 538 while (NextNode) { 539 N = NextNode; 540 PDB.LC = N->getLocationContext(); 541 NextNode = GetPredecessorNode(N); 542 543 ProgramPoint P = N->getLocation(); 544 545 do { 546 if (const CallExitEnd *CE = dyn_cast<CallExitEnd>(&P)) { 547 PathDiagnosticCallPiece *C = 548 PathDiagnosticCallPiece::construct(N, *CE, SMgr); 549 GRBugReporter& BR = PDB.getBugReporter(); 550 BR.addCallPieceLocationContextPair(C, CE->getCalleeContext()); 551 PD.getActivePath().push_front(C); 552 PD.pushActivePath(&C->path); 553 CallStack.push_back(StackDiagPair(C, N)); 554 break; 555 } 556 557 if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) { 558 // Flush all locations, and pop the active path. 559 bool VisitedEntireCall = PD.isWithinCall(); 560 PD.popActivePath(); 561 562 // Either we just added a bunch of stuff to the top-level path, or 563 // we have a previous CallExitEnd. If the former, it means that the 564 // path terminated within a function call. We must then take the 565 // current contents of the active path and place it within 566 // a new PathDiagnosticCallPiece. 567 PathDiagnosticCallPiece *C; 568 if (VisitedEntireCall) { 569 C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); 570 } else { 571 const Decl *Caller = CE->getLocationContext()->getDecl(); 572 C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 573 GRBugReporter& BR = PDB.getBugReporter(); 574 BR.addCallPieceLocationContextPair(C, CE->getCalleeContext()); 575 } 576 577 C->setCallee(*CE, SMgr); 578 if (!CallStack.empty()) { 579 assert(CallStack.back().first == C); 580 CallStack.pop_back(); 581 } 582 break; 583 } 584 585 if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { 586 const CFGBlock *Src = BE->getSrc(); 587 const CFGBlock *Dst = BE->getDst(); 588 const Stmt *T = Src->getTerminator(); 589 590 if (!T) 591 break; 592 593 PathDiagnosticLocation Start = 594 PathDiagnosticLocation::createBegin(T, SMgr, 595 N->getLocationContext()); 596 597 switch (T->getStmtClass()) { 598 default: 599 break; 600 601 case Stmt::GotoStmtClass: 602 case Stmt::IndirectGotoStmtClass: { 603 const Stmt *S = GetNextStmt(N); 604 605 if (!S) 606 break; 607 608 std::string sbuf; 609 llvm::raw_string_ostream os(sbuf); 610 const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S); 611 612 os << "Control jumps to line " 613 << End.asLocation().getExpansionLineNumber(); 614 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 615 Start, End, os.str())); 616 break; 617 } 618 619 case Stmt::SwitchStmtClass: { 620 // Figure out what case arm we took. 621 std::string sbuf; 622 llvm::raw_string_ostream os(sbuf); 623 624 if (const Stmt *S = Dst->getLabel()) { 625 PathDiagnosticLocation End(S, SMgr, LC); 626 627 switch (S->getStmtClass()) { 628 default: 629 os << "No cases match in the switch statement. " 630 "Control jumps to line " 631 << End.asLocation().getExpansionLineNumber(); 632 break; 633 case Stmt::DefaultStmtClass: 634 os << "Control jumps to the 'default' case at line " 635 << End.asLocation().getExpansionLineNumber(); 636 break; 637 638 case Stmt::CaseStmtClass: { 639 os << "Control jumps to 'case "; 640 const CaseStmt *Case = cast<CaseStmt>(S); 641 const Expr *LHS = Case->getLHS()->IgnoreParenCasts(); 642 643 // Determine if it is an enum. 644 bool GetRawInt = true; 645 646 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) { 647 // FIXME: Maybe this should be an assertion. Are there cases 648 // were it is not an EnumConstantDecl? 649 const EnumConstantDecl *D = 650 dyn_cast<EnumConstantDecl>(DR->getDecl()); 651 652 if (D) { 653 GetRawInt = false; 654 os << *D; 655 } 656 } 657 658 if (GetRawInt) 659 os << LHS->EvaluateKnownConstInt(PDB.getASTContext()); 660 661 os << ":' at line " 662 << End.asLocation().getExpansionLineNumber(); 663 break; 664 } 665 } 666 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 667 Start, End, os.str())); 668 } 669 else { 670 os << "'Default' branch taken. "; 671 const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N); 672 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 673 Start, End, os.str())); 674 } 675 676 break; 677 } 678 679 case Stmt::BreakStmtClass: 680 case Stmt::ContinueStmtClass: { 681 std::string sbuf; 682 llvm::raw_string_ostream os(sbuf); 683 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 684 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 685 Start, End, os.str())); 686 break; 687 } 688 689 // Determine control-flow for ternary '?'. 690 case Stmt::BinaryConditionalOperatorClass: 691 case Stmt::ConditionalOperatorClass: { 692 std::string sbuf; 693 llvm::raw_string_ostream os(sbuf); 694 os << "'?' condition is "; 695 696 if (*(Src->succ_begin()+1) == Dst) 697 os << "false"; 698 else 699 os << "true"; 700 701 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 702 703 if (const Stmt *S = End.asStmt()) 704 End = PDB.getEnclosingStmtLocation(S); 705 706 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 707 Start, End, os.str())); 708 break; 709 } 710 711 // Determine control-flow for short-circuited '&&' and '||'. 712 case Stmt::BinaryOperatorClass: { 713 if (!PDB.supportsLogicalOpControlFlow()) 714 break; 715 716 const BinaryOperator *B = cast<BinaryOperator>(T); 717 std::string sbuf; 718 llvm::raw_string_ostream os(sbuf); 719 os << "Left side of '"; 720 721 if (B->getOpcode() == BO_LAnd) { 722 os << "&&" << "' is "; 723 724 if (*(Src->succ_begin()+1) == Dst) { 725 os << "false"; 726 PathDiagnosticLocation End(B->getLHS(), SMgr, LC); 727 PathDiagnosticLocation Start = 728 PathDiagnosticLocation::createOperatorLoc(B, SMgr); 729 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 730 Start, End, os.str())); 731 } 732 else { 733 os << "true"; 734 PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); 735 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 736 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 737 Start, End, os.str())); 738 } 739 } 740 else { 741 assert(B->getOpcode() == BO_LOr); 742 os << "||" << "' is "; 743 744 if (*(Src->succ_begin()+1) == Dst) { 745 os << "false"; 746 PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); 747 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 748 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 749 Start, End, os.str())); 750 } 751 else { 752 os << "true"; 753 PathDiagnosticLocation End(B->getLHS(), SMgr, LC); 754 PathDiagnosticLocation Start = 755 PathDiagnosticLocation::createOperatorLoc(B, SMgr); 756 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 757 Start, End, os.str())); 758 } 759 } 760 761 break; 762 } 763 764 case Stmt::DoStmtClass: { 765 if (*(Src->succ_begin()) == Dst) { 766 std::string sbuf; 767 llvm::raw_string_ostream os(sbuf); 768 769 os << "Loop condition is true. "; 770 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 771 772 if (const Stmt *S = End.asStmt()) 773 End = PDB.getEnclosingStmtLocation(S); 774 775 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 776 Start, End, os.str())); 777 } 778 else { 779 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 780 781 if (const Stmt *S = End.asStmt()) 782 End = PDB.getEnclosingStmtLocation(S); 783 784 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 785 Start, End, "Loop condition is false. Exiting loop")); 786 } 787 788 break; 789 } 790 791 case Stmt::WhileStmtClass: 792 case Stmt::ForStmtClass: { 793 if (*(Src->succ_begin()+1) == Dst) { 794 std::string sbuf; 795 llvm::raw_string_ostream os(sbuf); 796 797 os << "Loop condition is false. "; 798 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 799 if (const Stmt *S = End.asStmt()) 800 End = PDB.getEnclosingStmtLocation(S); 801 802 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 803 Start, End, os.str())); 804 } 805 else { 806 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 807 if (const Stmt *S = End.asStmt()) 808 End = PDB.getEnclosingStmtLocation(S); 809 810 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 811 Start, End, "Loop condition is true. Entering loop body")); 812 } 813 814 break; 815 } 816 817 case Stmt::IfStmtClass: { 818 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 819 820 if (const Stmt *S = End.asStmt()) 821 End = PDB.getEnclosingStmtLocation(S); 822 823 if (*(Src->succ_begin()+1) == Dst) 824 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 825 Start, End, "Taking false branch")); 826 else 827 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 828 Start, End, "Taking true branch")); 829 830 break; 831 } 832 } 833 } 834 } while(0); 835 836 if (NextNode) { 837 // Add diagnostic pieces from custom visitors. 838 BugReport *R = PDB.getBugReport(); 839 for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(), 840 E = visitors.end(); 841 I != E; ++I) { 842 if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) { 843 PD.getActivePath().push_front(p); 844 updateStackPiecesWithMessage(p, CallStack); 845 } 846 } 847 } 848 } 849 850 if (!PDB.getBugReport()->isValid()) 851 return false; 852 853 // After constructing the full PathDiagnostic, do a pass over it to compact 854 // PathDiagnosticPieces that occur within a macro. 855 CompactPathDiagnostic(PD.getMutablePieces(), PDB.getSourceManager()); 856 return true; 857} 858 859//===----------------------------------------------------------------------===// 860// "Extensive" PathDiagnostic generation. 861//===----------------------------------------------------------------------===// 862 863static bool IsControlFlowExpr(const Stmt *S) { 864 const Expr *E = dyn_cast<Expr>(S); 865 866 if (!E) 867 return false; 868 869 E = E->IgnoreParenCasts(); 870 871 if (isa<AbstractConditionalOperator>(E)) 872 return true; 873 874 if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E)) 875 if (B->isLogicalOp()) 876 return true; 877 878 return false; 879} 880 881namespace { 882class ContextLocation : public PathDiagnosticLocation { 883 bool IsDead; 884public: 885 ContextLocation(const PathDiagnosticLocation &L, bool isdead = false) 886 : PathDiagnosticLocation(L), IsDead(isdead) {} 887 888 void markDead() { IsDead = true; } 889 bool isDead() const { return IsDead; } 890}; 891 892class EdgeBuilder { 893 std::vector<ContextLocation> CLocs; 894 typedef std::vector<ContextLocation>::iterator iterator; 895 PathDiagnostic &PD; 896 PathDiagnosticBuilder &PDB; 897 PathDiagnosticLocation PrevLoc; 898 899 bool IsConsumedExpr(const PathDiagnosticLocation &L); 900 901 bool containsLocation(const PathDiagnosticLocation &Container, 902 const PathDiagnosticLocation &Containee); 903 904 PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L); 905 906 PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L, 907 bool firstCharOnly = false) { 908 if (const Stmt *S = L.asStmt()) { 909 const Stmt *Original = S; 910 while (1) { 911 // Adjust the location for some expressions that are best referenced 912 // by one of their subexpressions. 913 switch (S->getStmtClass()) { 914 default: 915 break; 916 case Stmt::ParenExprClass: 917 case Stmt::GenericSelectionExprClass: 918 S = cast<Expr>(S)->IgnoreParens(); 919 firstCharOnly = true; 920 continue; 921 case Stmt::BinaryConditionalOperatorClass: 922 case Stmt::ConditionalOperatorClass: 923 S = cast<AbstractConditionalOperator>(S)->getCond(); 924 firstCharOnly = true; 925 continue; 926 case Stmt::ChooseExprClass: 927 S = cast<ChooseExpr>(S)->getCond(); 928 firstCharOnly = true; 929 continue; 930 case Stmt::BinaryOperatorClass: 931 S = cast<BinaryOperator>(S)->getLHS(); 932 firstCharOnly = true; 933 continue; 934 } 935 936 break; 937 } 938 939 if (S != Original) 940 L = PathDiagnosticLocation(S, L.getManager(), PDB.LC); 941 } 942 943 if (firstCharOnly) 944 L = PathDiagnosticLocation::createSingleLocation(L); 945 946 return L; 947 } 948 949 void popLocation() { 950 if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) { 951 // For contexts, we only one the first character as the range. 952 rawAddEdge(cleanUpLocation(CLocs.back(), true)); 953 } 954 CLocs.pop_back(); 955 } 956 957public: 958 EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb) 959 : PD(pd), PDB(pdb) { 960 961 // If the PathDiagnostic already has pieces, add the enclosing statement 962 // of the first piece as a context as well. 963 if (!PD.path.empty()) { 964 PrevLoc = (*PD.path.begin())->getLocation(); 965 966 if (const Stmt *S = PrevLoc.asStmt()) 967 addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 968 } 969 } 970 971 ~EdgeBuilder() { 972 while (!CLocs.empty()) popLocation(); 973 974 // Finally, add an initial edge from the start location of the first 975 // statement (if it doesn't already exist). 976 PathDiagnosticLocation L = PathDiagnosticLocation::createDeclBegin( 977 PDB.LC, 978 PDB.getSourceManager()); 979 if (L.isValid()) 980 rawAddEdge(L); 981 } 982 983 void flushLocations() { 984 while (!CLocs.empty()) 985 popLocation(); 986 PrevLoc = PathDiagnosticLocation(); 987 } 988 989 void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false); 990 991 void rawAddEdge(PathDiagnosticLocation NewLoc); 992 993 void addContext(const Stmt *S); 994 void addContext(const PathDiagnosticLocation &L); 995 void addExtendedContext(const Stmt *S); 996}; 997} // end anonymous namespace 998 999 1000PathDiagnosticLocation 1001EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) { 1002 if (const Stmt *S = L.asStmt()) { 1003 if (IsControlFlowExpr(S)) 1004 return L; 1005 1006 return PDB.getEnclosingStmtLocation(S); 1007 } 1008 1009 return L; 1010} 1011 1012bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container, 1013 const PathDiagnosticLocation &Containee) { 1014 1015 if (Container == Containee) 1016 return true; 1017 1018 if (Container.asDecl()) 1019 return true; 1020 1021 if (const Stmt *S = Containee.asStmt()) 1022 if (const Stmt *ContainerS = Container.asStmt()) { 1023 while (S) { 1024 if (S == ContainerS) 1025 return true; 1026 S = PDB.getParent(S); 1027 } 1028 return false; 1029 } 1030 1031 // Less accurate: compare using source ranges. 1032 SourceRange ContainerR = Container.asRange(); 1033 SourceRange ContaineeR = Containee.asRange(); 1034 1035 SourceManager &SM = PDB.getSourceManager(); 1036 SourceLocation ContainerRBeg = SM.getExpansionLoc(ContainerR.getBegin()); 1037 SourceLocation ContainerREnd = SM.getExpansionLoc(ContainerR.getEnd()); 1038 SourceLocation ContaineeRBeg = SM.getExpansionLoc(ContaineeR.getBegin()); 1039 SourceLocation ContaineeREnd = SM.getExpansionLoc(ContaineeR.getEnd()); 1040 1041 unsigned ContainerBegLine = SM.getExpansionLineNumber(ContainerRBeg); 1042 unsigned ContainerEndLine = SM.getExpansionLineNumber(ContainerREnd); 1043 unsigned ContaineeBegLine = SM.getExpansionLineNumber(ContaineeRBeg); 1044 unsigned ContaineeEndLine = SM.getExpansionLineNumber(ContaineeREnd); 1045 1046 assert(ContainerBegLine <= ContainerEndLine); 1047 assert(ContaineeBegLine <= ContaineeEndLine); 1048 1049 return (ContainerBegLine <= ContaineeBegLine && 1050 ContainerEndLine >= ContaineeEndLine && 1051 (ContainerBegLine != ContaineeBegLine || 1052 SM.getExpansionColumnNumber(ContainerRBeg) <= 1053 SM.getExpansionColumnNumber(ContaineeRBeg)) && 1054 (ContainerEndLine != ContaineeEndLine || 1055 SM.getExpansionColumnNumber(ContainerREnd) >= 1056 SM.getExpansionColumnNumber(ContaineeREnd))); 1057} 1058 1059void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) { 1060 if (!PrevLoc.isValid()) { 1061 PrevLoc = NewLoc; 1062 return; 1063 } 1064 1065 const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc); 1066 const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc); 1067 1068 if (PrevLocClean.asLocation().isInvalid()) { 1069 PrevLoc = NewLoc; 1070 return; 1071 } 1072 1073 if (NewLocClean.asLocation() == PrevLocClean.asLocation()) 1074 return; 1075 1076 // FIXME: Ignore intra-macro edges for now. 1077 if (NewLocClean.asLocation().getExpansionLoc() == 1078 PrevLocClean.asLocation().getExpansionLoc()) 1079 return; 1080 1081 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean)); 1082 PrevLoc = NewLoc; 1083} 1084 1085void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd) { 1086 1087 if (!alwaysAdd && NewLoc.asLocation().isMacroID()) 1088 return; 1089 1090 const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc); 1091 1092 while (!CLocs.empty()) { 1093 ContextLocation &TopContextLoc = CLocs.back(); 1094 1095 // Is the top location context the same as the one for the new location? 1096 if (TopContextLoc == CLoc) { 1097 if (alwaysAdd) { 1098 if (IsConsumedExpr(TopContextLoc) && 1099 !IsControlFlowExpr(TopContextLoc.asStmt())) 1100 TopContextLoc.markDead(); 1101 1102 rawAddEdge(NewLoc); 1103 } 1104 1105 return; 1106 } 1107 1108 if (containsLocation(TopContextLoc, CLoc)) { 1109 if (alwaysAdd) { 1110 rawAddEdge(NewLoc); 1111 1112 if (IsConsumedExpr(CLoc) && !IsControlFlowExpr(CLoc.asStmt())) { 1113 CLocs.push_back(ContextLocation(CLoc, true)); 1114 return; 1115 } 1116 } 1117 1118 CLocs.push_back(CLoc); 1119 return; 1120 } 1121 1122 // Context does not contain the location. Flush it. 1123 popLocation(); 1124 } 1125 1126 // If we reach here, there is no enclosing context. Just add the edge. 1127 rawAddEdge(NewLoc); 1128} 1129 1130bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) { 1131 if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt())) 1132 return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X); 1133 1134 return false; 1135} 1136 1137void EdgeBuilder::addExtendedContext(const Stmt *S) { 1138 if (!S) 1139 return; 1140 1141 const Stmt *Parent = PDB.getParent(S); 1142 while (Parent) { 1143 if (isa<CompoundStmt>(Parent)) 1144 Parent = PDB.getParent(Parent); 1145 else 1146 break; 1147 } 1148 1149 if (Parent) { 1150 switch (Parent->getStmtClass()) { 1151 case Stmt::DoStmtClass: 1152 case Stmt::ObjCAtSynchronizedStmtClass: 1153 addContext(Parent); 1154 default: 1155 break; 1156 } 1157 } 1158 1159 addContext(S); 1160} 1161 1162void EdgeBuilder::addContext(const Stmt *S) { 1163 if (!S) 1164 return; 1165 1166 PathDiagnosticLocation L(S, PDB.getSourceManager(), PDB.LC); 1167 addContext(L); 1168} 1169 1170void EdgeBuilder::addContext(const PathDiagnosticLocation &L) { 1171 while (!CLocs.empty()) { 1172 const PathDiagnosticLocation &TopContextLoc = CLocs.back(); 1173 1174 // Is the top location context the same as the one for the new location? 1175 if (TopContextLoc == L) 1176 return; 1177 1178 if (containsLocation(TopContextLoc, L)) { 1179 CLocs.push_back(L); 1180 return; 1181 } 1182 1183 // Context does not contain the location. Flush it. 1184 popLocation(); 1185 } 1186 1187 CLocs.push_back(L); 1188} 1189 1190// Cone-of-influence: support the reverse propagation of "interesting" symbols 1191// and values by tracing interesting calculations backwards through evaluated 1192// expressions along a path. This is probably overly complicated, but the idea 1193// is that if an expression computed an "interesting" value, the child 1194// expressions are are also likely to be "interesting" as well (which then 1195// propagates to the values they in turn compute). This reverse propagation 1196// is needed to track interesting correlations across function call boundaries, 1197// where formal arguments bind to actual arguments, etc. This is also needed 1198// because the constraint solver sometimes simplifies certain symbolic values 1199// into constants when appropriate, and this complicates reasoning about 1200// interesting values. 1201typedef llvm::DenseSet<const Expr *> InterestingExprs; 1202 1203static void reversePropagateIntererstingSymbols(BugReport &R, 1204 InterestingExprs &IE, 1205 const ProgramState *State, 1206 const Expr *Ex, 1207 const LocationContext *LCtx) { 1208 SVal V = State->getSVal(Ex, LCtx); 1209 if (!(R.isInteresting(V) || IE.count(Ex))) 1210 return; 1211 1212 switch (Ex->getStmtClass()) { 1213 default: 1214 if (!isa<CastExpr>(Ex)) 1215 break; 1216 // Fall through. 1217 case Stmt::BinaryOperatorClass: 1218 case Stmt::UnaryOperatorClass: { 1219 for (Stmt::const_child_iterator CI = Ex->child_begin(), 1220 CE = Ex->child_end(); 1221 CI != CE; ++CI) { 1222 if (const Expr *child = dyn_cast_or_null<Expr>(*CI)) { 1223 IE.insert(child); 1224 SVal ChildV = State->getSVal(child, LCtx); 1225 R.markInteresting(ChildV); 1226 } 1227 break; 1228 } 1229 } 1230 } 1231 1232 R.markInteresting(V); 1233} 1234 1235static void reversePropagateInterestingSymbols(BugReport &R, 1236 InterestingExprs &IE, 1237 const ProgramState *State, 1238 const LocationContext *CalleeCtx, 1239 const LocationContext *CallerCtx) 1240{ 1241 // FIXME: Handle non-CallExpr-based CallEvents. 1242 const StackFrameContext *Callee = CalleeCtx->getCurrentStackFrame(); 1243 const Stmt *CallSite = Callee->getCallSite(); 1244 if (const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite)) { 1245 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CalleeCtx->getDecl())) { 1246 FunctionDecl::param_const_iterator PI = FD->param_begin(), 1247 PE = FD->param_end(); 1248 CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end(); 1249 for (; AI != AE && PI != PE; ++AI, ++PI) { 1250 if (const Expr *ArgE = *AI) { 1251 if (const ParmVarDecl *PD = *PI) { 1252 Loc LV = State->getLValue(PD, CalleeCtx); 1253 if (R.isInteresting(LV) || R.isInteresting(State->getRawSVal(LV))) 1254 IE.insert(ArgE); 1255 } 1256 } 1257 } 1258 } 1259 } 1260} 1261 1262static bool GenerateExtensivePathDiagnostic(PathDiagnostic& PD, 1263 PathDiagnosticBuilder &PDB, 1264 const ExplodedNode *N, 1265 ArrayRef<BugReporterVisitor *> visitors) { 1266 EdgeBuilder EB(PD, PDB); 1267 const SourceManager& SM = PDB.getSourceManager(); 1268 StackDiagVector CallStack; 1269 InterestingExprs IE; 1270 1271 const ExplodedNode *NextNode = N->pred_empty() ? NULL : *(N->pred_begin()); 1272 while (NextNode) { 1273 N = NextNode; 1274 NextNode = GetPredecessorNode(N); 1275 ProgramPoint P = N->getLocation(); 1276 1277 do { 1278 if (const PostStmt *PS = dyn_cast<PostStmt>(&P)) { 1279 if (const Expr *Ex = PS->getStmtAs<Expr>()) 1280 reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1281 N->getState().getPtr(), Ex, 1282 N->getLocationContext()); 1283 } 1284 1285 if (const CallExitEnd *CE = dyn_cast<CallExitEnd>(&P)) { 1286 const Stmt *S = CE->getCalleeContext()->getCallSite(); 1287 if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) { 1288 reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1289 N->getState().getPtr(), Ex, 1290 N->getLocationContext()); 1291 } 1292 1293 PathDiagnosticCallPiece *C = 1294 PathDiagnosticCallPiece::construct(N, *CE, SM); 1295 GRBugReporter& BR = PDB.getBugReporter(); 1296 BR.addCallPieceLocationContextPair(C, CE->getCalleeContext()); 1297 1298 EB.addEdge(C->callReturn, true); 1299 EB.flushLocations(); 1300 1301 PD.getActivePath().push_front(C); 1302 PD.pushActivePath(&C->path); 1303 CallStack.push_back(StackDiagPair(C, N)); 1304 break; 1305 } 1306 1307 // Pop the call hierarchy if we are done walking the contents 1308 // of a function call. 1309 if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) { 1310 // Add an edge to the start of the function. 1311 const Decl *D = CE->getCalleeContext()->getDecl(); 1312 PathDiagnosticLocation pos = 1313 PathDiagnosticLocation::createBegin(D, SM); 1314 EB.addEdge(pos); 1315 1316 // Flush all locations, and pop the active path. 1317 bool VisitedEntireCall = PD.isWithinCall(); 1318 EB.flushLocations(); 1319 PD.popActivePath(); 1320 PDB.LC = N->getLocationContext(); 1321 1322 // Either we just added a bunch of stuff to the top-level path, or 1323 // we have a previous CallExitEnd. If the former, it means that the 1324 // path terminated within a function call. We must then take the 1325 // current contents of the active path and place it within 1326 // a new PathDiagnosticCallPiece. 1327 PathDiagnosticCallPiece *C; 1328 if (VisitedEntireCall) { 1329 C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); 1330 } else { 1331 const Decl *Caller = CE->getLocationContext()->getDecl(); 1332 C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 1333 GRBugReporter& BR = PDB.getBugReporter(); 1334 BR.addCallPieceLocationContextPair(C, CE->getCalleeContext()); 1335 } 1336 1337 C->setCallee(*CE, SM); 1338 EB.addContext(C->getLocation()); 1339 1340 if (!CallStack.empty()) { 1341 assert(CallStack.back().first == C); 1342 CallStack.pop_back(); 1343 } 1344 break; 1345 } 1346 1347 // Note that is important that we update the LocationContext 1348 // after looking at CallExits. CallExit basically adds an 1349 // edge in the *caller*, so we don't want to update the LocationContext 1350 // too soon. 1351 PDB.LC = N->getLocationContext(); 1352 1353 // Block edges. 1354 if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { 1355 // Does this represent entering a call? If so, look at propagating 1356 // interesting symbols across call boundaries. 1357 if (NextNode) { 1358 const LocationContext *CallerCtx = NextNode->getLocationContext(); 1359 const LocationContext *CalleeCtx = PDB.LC; 1360 if (CallerCtx != CalleeCtx) { 1361 reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, 1362 N->getState().getPtr(), 1363 CalleeCtx, CallerCtx); 1364 } 1365 } 1366 1367 // Are we jumping to the head of a loop? Add a special diagnostic. 1368 if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { 1369 PathDiagnosticLocation L(Loop, SM, PDB.LC); 1370 const CompoundStmt *CS = NULL; 1371 1372 if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) 1373 CS = dyn_cast<CompoundStmt>(FS->getBody()); 1374 else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) 1375 CS = dyn_cast<CompoundStmt>(WS->getBody()); 1376 1377 PathDiagnosticEventPiece *p = 1378 new PathDiagnosticEventPiece(L, 1379 "Looping back to the head of the loop"); 1380 p->setPrunable(true); 1381 1382 EB.addEdge(p->getLocation(), true); 1383 PD.getActivePath().push_front(p); 1384 1385 if (CS) { 1386 PathDiagnosticLocation BL = 1387 PathDiagnosticLocation::createEndBrace(CS, SM); 1388 EB.addEdge(BL); 1389 } 1390 } 1391 1392 if (const Stmt *Term = BE->getSrc()->getTerminator()) 1393 EB.addContext(Term); 1394 1395 break; 1396 } 1397 1398 if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) { 1399 CFGElement First = BE->getFirstElement(); 1400 if (const CFGStmt *S = First.getAs<CFGStmt>()) { 1401 const Stmt *stmt = S->getStmt(); 1402 if (IsControlFlowExpr(stmt)) { 1403 // Add the proper context for '&&', '||', and '?'. 1404 EB.addContext(stmt); 1405 } 1406 else 1407 EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt()); 1408 } 1409 1410 break; 1411 } 1412 1413 1414 } while (0); 1415 1416 if (!NextNode) 1417 continue; 1418 1419 // Add pieces from custom visitors. 1420 BugReport *R = PDB.getBugReport(); 1421 for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(), 1422 E = visitors.end(); 1423 I != E; ++I) { 1424 if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) { 1425 const PathDiagnosticLocation &Loc = p->getLocation(); 1426 EB.addEdge(Loc, true); 1427 PD.getActivePath().push_front(p); 1428 updateStackPiecesWithMessage(p, CallStack); 1429 1430 if (const Stmt *S = Loc.asStmt()) 1431 EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 1432 } 1433 } 1434 } 1435 1436 return PDB.getBugReport()->isValid(); 1437} 1438 1439//===----------------------------------------------------------------------===// 1440// Methods for BugType and subclasses. 1441//===----------------------------------------------------------------------===// 1442BugType::~BugType() { } 1443 1444void BugType::FlushReports(BugReporter &BR) {} 1445 1446void BuiltinBug::anchor() {} 1447 1448//===----------------------------------------------------------------------===// 1449// Methods for BugReport and subclasses. 1450//===----------------------------------------------------------------------===// 1451 1452void BugReport::NodeResolver::anchor() {} 1453 1454void BugReport::addVisitor(BugReporterVisitor* visitor) { 1455 if (!visitor) 1456 return; 1457 1458 llvm::FoldingSetNodeID ID; 1459 visitor->Profile(ID); 1460 void *InsertPos; 1461 1462 if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) { 1463 delete visitor; 1464 return; 1465 } 1466 1467 CallbacksSet.InsertNode(visitor, InsertPos); 1468 Callbacks.push_back(visitor); 1469 ++ConfigurationChangeToken; 1470} 1471 1472BugReport::~BugReport() { 1473 for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I) { 1474 delete *I; 1475 } 1476 while (!interestingSymbols.empty()) { 1477 popInterestingSymbolsAndRegions(); 1478 } 1479} 1480 1481const Decl *BugReport::getDeclWithIssue() const { 1482 if (DeclWithIssue) 1483 return DeclWithIssue; 1484 1485 const ExplodedNode *N = getErrorNode(); 1486 if (!N) 1487 return 0; 1488 1489 const LocationContext *LC = N->getLocationContext(); 1490 return LC->getCurrentStackFrame()->getDecl(); 1491} 1492 1493void BugReport::Profile(llvm::FoldingSetNodeID& hash) const { 1494 hash.AddPointer(&BT); 1495 hash.AddString(Description); 1496 if (UniqueingLocation.isValid()) { 1497 UniqueingLocation.Profile(hash); 1498 } else if (Location.isValid()) { 1499 Location.Profile(hash); 1500 } else { 1501 assert(ErrorNode); 1502 hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode)); 1503 } 1504 1505 for (SmallVectorImpl<SourceRange>::const_iterator I = 1506 Ranges.begin(), E = Ranges.end(); I != E; ++I) { 1507 const SourceRange range = *I; 1508 if (!range.isValid()) 1509 continue; 1510 hash.AddInteger(range.getBegin().getRawEncoding()); 1511 hash.AddInteger(range.getEnd().getRawEncoding()); 1512 } 1513} 1514 1515void BugReport::markInteresting(SymbolRef sym) { 1516 if (!sym) 1517 return; 1518 1519 // If the symbol wasn't already in our set, note a configuration change. 1520 if (getInterestingSymbols().insert(sym).second) 1521 ++ConfigurationChangeToken; 1522 1523 if (const SymbolMetadata *meta = dyn_cast<SymbolMetadata>(sym)) 1524 getInterestingRegions().insert(meta->getRegion()); 1525} 1526 1527void BugReport::markInteresting(const MemRegion *R) { 1528 if (!R) 1529 return; 1530 1531 // If the base region wasn't already in our set, note a configuration change. 1532 R = R->getBaseRegion(); 1533 if (getInterestingRegions().insert(R).second) 1534 ++ConfigurationChangeToken; 1535 1536 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 1537 getInterestingSymbols().insert(SR->getSymbol()); 1538} 1539 1540void BugReport::markInteresting(SVal V) { 1541 markInteresting(V.getAsRegion()); 1542 markInteresting(V.getAsSymbol()); 1543} 1544 1545void BugReport::markInteresting(const LocationContext *LC) { 1546 if (!LC) 1547 return; 1548 InterestingLocationContexts.insert(LC); 1549} 1550 1551bool BugReport::isInteresting(SVal V) { 1552 return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol()); 1553} 1554 1555bool BugReport::isInteresting(SymbolRef sym) { 1556 if (!sym) 1557 return false; 1558 // We don't currently consider metadata symbols to be interesting 1559 // even if we know their region is interesting. Is that correct behavior? 1560 return getInterestingSymbols().count(sym); 1561} 1562 1563bool BugReport::isInteresting(const MemRegion *R) { 1564 if (!R) 1565 return false; 1566 R = R->getBaseRegion(); 1567 bool b = getInterestingRegions().count(R); 1568 if (b) 1569 return true; 1570 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 1571 return getInterestingSymbols().count(SR->getSymbol()); 1572 return false; 1573} 1574 1575bool BugReport::isInteresting(const LocationContext *LC) { 1576 if (!LC) 1577 return false; 1578 return InterestingLocationContexts.count(LC); 1579} 1580 1581void BugReport::lazyInitializeInterestingSets() { 1582 if (interestingSymbols.empty()) { 1583 interestingSymbols.push_back(new Symbols()); 1584 interestingRegions.push_back(new Regions()); 1585 } 1586} 1587 1588BugReport::Symbols &BugReport::getInterestingSymbols() { 1589 lazyInitializeInterestingSets(); 1590 return *interestingSymbols.back(); 1591} 1592 1593BugReport::Regions &BugReport::getInterestingRegions() { 1594 lazyInitializeInterestingSets(); 1595 return *interestingRegions.back(); 1596} 1597 1598void BugReport::pushInterestingSymbolsAndRegions() { 1599 interestingSymbols.push_back(new Symbols(getInterestingSymbols())); 1600 interestingRegions.push_back(new Regions(getInterestingRegions())); 1601} 1602 1603void BugReport::popInterestingSymbolsAndRegions() { 1604 delete interestingSymbols.back(); 1605 interestingSymbols.pop_back(); 1606 delete interestingRegions.back(); 1607 interestingRegions.pop_back(); 1608} 1609 1610const Stmt *BugReport::getStmt() const { 1611 if (!ErrorNode) 1612 return 0; 1613 1614 ProgramPoint ProgP = ErrorNode->getLocation(); 1615 const Stmt *S = NULL; 1616 1617 if (BlockEntrance *BE = dyn_cast<BlockEntrance>(&ProgP)) { 1618 CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit(); 1619 if (BE->getBlock() == &Exit) 1620 S = GetPreviousStmt(ErrorNode); 1621 } 1622 if (!S) 1623 S = GetStmt(ProgP); 1624 1625 return S; 1626} 1627 1628std::pair<BugReport::ranges_iterator, BugReport::ranges_iterator> 1629BugReport::getRanges() { 1630 // If no custom ranges, add the range of the statement corresponding to 1631 // the error node. 1632 if (Ranges.empty()) { 1633 if (const Expr *E = dyn_cast_or_null<Expr>(getStmt())) 1634 addRange(E->getSourceRange()); 1635 else 1636 return std::make_pair(ranges_iterator(), ranges_iterator()); 1637 } 1638 1639 // User-specified absence of range info. 1640 if (Ranges.size() == 1 && !Ranges.begin()->isValid()) 1641 return std::make_pair(ranges_iterator(), ranges_iterator()); 1642 1643 return std::make_pair(Ranges.begin(), Ranges.end()); 1644} 1645 1646PathDiagnosticLocation BugReport::getLocation(const SourceManager &SM) const { 1647 if (ErrorNode) { 1648 assert(!Location.isValid() && 1649 "Either Location or ErrorNode should be specified but not both."); 1650 1651 if (const Stmt *S = GetCurrentOrPreviousStmt(ErrorNode)) { 1652 const LocationContext *LC = ErrorNode->getLocationContext(); 1653 1654 // For member expressions, return the location of the '.' or '->'. 1655 if (const MemberExpr *ME = dyn_cast<MemberExpr>(S)) 1656 return PathDiagnosticLocation::createMemberLoc(ME, SM); 1657 // For binary operators, return the location of the operator. 1658 if (const BinaryOperator *B = dyn_cast<BinaryOperator>(S)) 1659 return PathDiagnosticLocation::createOperatorLoc(B, SM); 1660 1661 return PathDiagnosticLocation::createBegin(S, SM, LC); 1662 } 1663 } else { 1664 assert(Location.isValid()); 1665 return Location; 1666 } 1667 1668 return PathDiagnosticLocation(); 1669} 1670 1671//===----------------------------------------------------------------------===// 1672// Methods for BugReporter and subclasses. 1673//===----------------------------------------------------------------------===// 1674 1675BugReportEquivClass::~BugReportEquivClass() { } 1676GRBugReporter::~GRBugReporter() { } 1677BugReporterData::~BugReporterData() {} 1678 1679ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); } 1680 1681ProgramStateManager& 1682GRBugReporter::getStateManager() { return Eng.getStateManager(); } 1683 1684BugReporter::~BugReporter() { 1685 FlushReports(); 1686 1687 // Free the bug reports we are tracking. 1688 typedef std::vector<BugReportEquivClass *> ContTy; 1689 for (ContTy::iterator I = EQClassesVector.begin(), E = EQClassesVector.end(); 1690 I != E; ++I) { 1691 delete *I; 1692 } 1693} 1694 1695void BugReporter::FlushReports() { 1696 if (BugTypes.isEmpty()) 1697 return; 1698 1699 // First flush the warnings for each BugType. This may end up creating new 1700 // warnings and new BugTypes. 1701 // FIXME: Only NSErrorChecker needs BugType's FlushReports. 1702 // Turn NSErrorChecker into a proper checker and remove this. 1703 SmallVector<const BugType*, 16> bugTypes; 1704 for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I) 1705 bugTypes.push_back(*I); 1706 for (SmallVector<const BugType*, 16>::iterator 1707 I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I) 1708 const_cast<BugType*>(*I)->FlushReports(*this); 1709 1710 // We need to flush reports in deterministic order to ensure the order 1711 // of the reports is consistent between runs. 1712 typedef std::vector<BugReportEquivClass *> ContVecTy; 1713 for (ContVecTy::iterator EI=EQClassesVector.begin(), EE=EQClassesVector.end(); 1714 EI != EE; ++EI){ 1715 BugReportEquivClass& EQ = **EI; 1716 FlushReport(EQ); 1717 } 1718 1719 // BugReporter owns and deletes only BugTypes created implicitly through 1720 // EmitBasicReport. 1721 // FIXME: There are leaks from checkers that assume that the BugTypes they 1722 // create will be destroyed by the BugReporter. 1723 for (llvm::StringMap<BugType*>::iterator 1724 I = StrBugTypes.begin(), E = StrBugTypes.end(); I != E; ++I) 1725 delete I->second; 1726 1727 // Remove all references to the BugType objects. 1728 BugTypes = F.getEmptySet(); 1729} 1730 1731//===----------------------------------------------------------------------===// 1732// PathDiagnostics generation. 1733//===----------------------------------------------------------------------===// 1734 1735static std::pair<std::pair<ExplodedGraph*, NodeBackMap*>, 1736 std::pair<ExplodedNode*, unsigned> > 1737MakeReportGraph(const ExplodedGraph* G, 1738 SmallVectorImpl<const ExplodedNode*> &nodes) { 1739 1740 // Create the trimmed graph. It will contain the shortest paths from the 1741 // error nodes to the root. In the new graph we should only have one 1742 // error node unless there are two or more error nodes with the same minimum 1743 // path length. 1744 ExplodedGraph* GTrim; 1745 InterExplodedGraphMap* NMap; 1746 1747 llvm::DenseMap<const void*, const void*> InverseMap; 1748 llvm::tie(GTrim, NMap) = G->Trim(nodes.data(), nodes.data() + nodes.size(), 1749 &InverseMap); 1750 1751 // Create owning pointers for GTrim and NMap just to ensure that they are 1752 // released when this function exists. 1753 OwningPtr<ExplodedGraph> AutoReleaseGTrim(GTrim); 1754 OwningPtr<InterExplodedGraphMap> AutoReleaseNMap(NMap); 1755 1756 // Find the (first) error node in the trimmed graph. We just need to consult 1757 // the node map (NMap) which maps from nodes in the original graph to nodes 1758 // in the new graph. 1759 1760 std::queue<const ExplodedNode*> WS; 1761 typedef llvm::DenseMap<const ExplodedNode*, unsigned> IndexMapTy; 1762 IndexMapTy IndexMap; 1763 1764 for (unsigned nodeIndex = 0 ; nodeIndex < nodes.size(); ++nodeIndex) { 1765 const ExplodedNode *originalNode = nodes[nodeIndex]; 1766 if (const ExplodedNode *N = NMap->getMappedNode(originalNode)) { 1767 WS.push(N); 1768 IndexMap[originalNode] = nodeIndex; 1769 } 1770 } 1771 1772 assert(!WS.empty() && "No error node found in the trimmed graph."); 1773 1774 // Create a new (third!) graph with a single path. This is the graph 1775 // that will be returned to the caller. 1776 ExplodedGraph *GNew = new ExplodedGraph(); 1777 1778 // Sometimes the trimmed graph can contain a cycle. Perform a reverse BFS 1779 // to the root node, and then construct a new graph that contains only 1780 // a single path. 1781 llvm::DenseMap<const void*,unsigned> Visited; 1782 1783 unsigned cnt = 0; 1784 const ExplodedNode *Root = 0; 1785 1786 while (!WS.empty()) { 1787 const ExplodedNode *Node = WS.front(); 1788 WS.pop(); 1789 1790 if (Visited.find(Node) != Visited.end()) 1791 continue; 1792 1793 Visited[Node] = cnt++; 1794 1795 if (Node->pred_empty()) { 1796 Root = Node; 1797 break; 1798 } 1799 1800 for (ExplodedNode::const_pred_iterator I=Node->pred_begin(), 1801 E=Node->pred_end(); I!=E; ++I) 1802 WS.push(*I); 1803 } 1804 1805 assert(Root); 1806 1807 // Now walk from the root down the BFS path, always taking the successor 1808 // with the lowest number. 1809 ExplodedNode *Last = 0, *First = 0; 1810 NodeBackMap *BM = new NodeBackMap(); 1811 unsigned NodeIndex = 0; 1812 1813 for ( const ExplodedNode *N = Root ;;) { 1814 // Lookup the number associated with the current node. 1815 llvm::DenseMap<const void*,unsigned>::iterator I = Visited.find(N); 1816 assert(I != Visited.end()); 1817 1818 // Create the equivalent node in the new graph with the same state 1819 // and location. 1820 ExplodedNode *NewN = GNew->getNode(N->getLocation(), N->getState()); 1821 1822 // Store the mapping to the original node. 1823 llvm::DenseMap<const void*, const void*>::iterator IMitr=InverseMap.find(N); 1824 assert(IMitr != InverseMap.end() && "No mapping to original node."); 1825 (*BM)[NewN] = (const ExplodedNode*) IMitr->second; 1826 1827 // Link up the new node with the previous node. 1828 if (Last) 1829 NewN->addPredecessor(Last, *GNew); 1830 1831 Last = NewN; 1832 1833 // Are we at the final node? 1834 IndexMapTy::iterator IMI = 1835 IndexMap.find((const ExplodedNode*)(IMitr->second)); 1836 if (IMI != IndexMap.end()) { 1837 First = NewN; 1838 NodeIndex = IMI->second; 1839 break; 1840 } 1841 1842 // Find the next successor node. We choose the node that is marked 1843 // with the lowest DFS number. 1844 ExplodedNode::const_succ_iterator SI = N->succ_begin(); 1845 ExplodedNode::const_succ_iterator SE = N->succ_end(); 1846 N = 0; 1847 1848 for (unsigned MinVal = 0; SI != SE; ++SI) { 1849 1850 I = Visited.find(*SI); 1851 1852 if (I == Visited.end()) 1853 continue; 1854 1855 if (!N || I->second < MinVal) { 1856 N = *SI; 1857 MinVal = I->second; 1858 } 1859 } 1860 1861 assert(N); 1862 } 1863 1864 assert(First); 1865 1866 return std::make_pair(std::make_pair(GNew, BM), 1867 std::make_pair(First, NodeIndex)); 1868} 1869 1870/// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object 1871/// and collapses PathDiagosticPieces that are expanded by macros. 1872static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) { 1873 typedef std::vector<std::pair<IntrusiveRefCntPtr<PathDiagnosticMacroPiece>, 1874 SourceLocation> > MacroStackTy; 1875 1876 typedef std::vector<IntrusiveRefCntPtr<PathDiagnosticPiece> > 1877 PiecesTy; 1878 1879 MacroStackTy MacroStack; 1880 PiecesTy Pieces; 1881 1882 for (PathPieces::const_iterator I = path.begin(), E = path.end(); 1883 I!=E; ++I) { 1884 1885 PathDiagnosticPiece *piece = I->getPtr(); 1886 1887 // Recursively compact calls. 1888 if (PathDiagnosticCallPiece *call=dyn_cast<PathDiagnosticCallPiece>(piece)){ 1889 CompactPathDiagnostic(call->path, SM); 1890 } 1891 1892 // Get the location of the PathDiagnosticPiece. 1893 const FullSourceLoc Loc = piece->getLocation().asLocation(); 1894 1895 // Determine the instantiation location, which is the location we group 1896 // related PathDiagnosticPieces. 1897 SourceLocation InstantiationLoc = Loc.isMacroID() ? 1898 SM.getExpansionLoc(Loc) : 1899 SourceLocation(); 1900 1901 if (Loc.isFileID()) { 1902 MacroStack.clear(); 1903 Pieces.push_back(piece); 1904 continue; 1905 } 1906 1907 assert(Loc.isMacroID()); 1908 1909 // Is the PathDiagnosticPiece within the same macro group? 1910 if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) { 1911 MacroStack.back().first->subPieces.push_back(piece); 1912 continue; 1913 } 1914 1915 // We aren't in the same group. Are we descending into a new macro 1916 // or are part of an old one? 1917 IntrusiveRefCntPtr<PathDiagnosticMacroPiece> MacroGroup; 1918 1919 SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ? 1920 SM.getExpansionLoc(Loc) : 1921 SourceLocation(); 1922 1923 // Walk the entire macro stack. 1924 while (!MacroStack.empty()) { 1925 if (InstantiationLoc == MacroStack.back().second) { 1926 MacroGroup = MacroStack.back().first; 1927 break; 1928 } 1929 1930 if (ParentInstantiationLoc == MacroStack.back().second) { 1931 MacroGroup = MacroStack.back().first; 1932 break; 1933 } 1934 1935 MacroStack.pop_back(); 1936 } 1937 1938 if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) { 1939 // Create a new macro group and add it to the stack. 1940 PathDiagnosticMacroPiece *NewGroup = 1941 new PathDiagnosticMacroPiece( 1942 PathDiagnosticLocation::createSingleLocation(piece->getLocation())); 1943 1944 if (MacroGroup) 1945 MacroGroup->subPieces.push_back(NewGroup); 1946 else { 1947 assert(InstantiationLoc.isFileID()); 1948 Pieces.push_back(NewGroup); 1949 } 1950 1951 MacroGroup = NewGroup; 1952 MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc)); 1953 } 1954 1955 // Finally, add the PathDiagnosticPiece to the group. 1956 MacroGroup->subPieces.push_back(piece); 1957 } 1958 1959 // Now take the pieces and construct a new PathDiagnostic. 1960 path.clear(); 1961 1962 for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I) 1963 path.push_back(*I); 1964} 1965 1966bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD, 1967 PathDiagnosticConsumer &PC, 1968 ArrayRef<BugReport *> &bugReports) { 1969 assert(!bugReports.empty()); 1970 1971 bool HasValid = false; 1972 SmallVector<const ExplodedNode *, 10> errorNodes; 1973 for (ArrayRef<BugReport*>::iterator I = bugReports.begin(), 1974 E = bugReports.end(); I != E; ++I) { 1975 if ((*I)->isValid()) { 1976 HasValid = true; 1977 errorNodes.push_back((*I)->getErrorNode()); 1978 } else { 1979 errorNodes.push_back(0); 1980 } 1981 } 1982 1983 // If all the reports have been marked invalid, we're done. 1984 if (!HasValid) 1985 return false; 1986 1987 // Construct a new graph that contains only a single path from the error 1988 // node to a root. 1989 const std::pair<std::pair<ExplodedGraph*, NodeBackMap*>, 1990 std::pair<ExplodedNode*, unsigned> >& 1991 GPair = MakeReportGraph(&getGraph(), errorNodes); 1992 1993 // Find the BugReport with the original location. 1994 assert(GPair.second.second < bugReports.size()); 1995 BugReport *R = bugReports[GPair.second.second]; 1996 assert(R && "No original report found for sliced graph."); 1997 assert(R->isValid() && "Report selected from trimmed graph marked invalid."); 1998 1999 OwningPtr<ExplodedGraph> ReportGraph(GPair.first.first); 2000 OwningPtr<NodeBackMap> BackMap(GPair.first.second); 2001 const ExplodedNode *N = GPair.second.first; 2002 2003 // Start building the path diagnostic... 2004 PathDiagnosticBuilder PDB(*this, R, BackMap.get(), &PC); 2005 2006 // Register additional node visitors. 2007 R->addVisitor(new NilReceiverBRVisitor()); 2008 R->addVisitor(new ConditionBRVisitor()); 2009 2010 BugReport::VisitorList visitors; 2011 unsigned originalReportConfigToken, finalReportConfigToken; 2012 2013 // While generating diagnostics, it's possible the visitors will decide 2014 // new symbols and regions are interesting, or add other visitors based on 2015 // the information they find. If they do, we need to regenerate the path 2016 // based on our new report configuration. 2017 do { 2018 // Get a clean copy of all the visitors. 2019 for (BugReport::visitor_iterator I = R->visitor_begin(), 2020 E = R->visitor_end(); I != E; ++I) 2021 visitors.push_back((*I)->clone()); 2022 2023 // Clear out the active path from any previous work. 2024 PD.resetPath(); 2025 originalReportConfigToken = R->getConfigurationChangeToken(); 2026 2027 // Generate the very last diagnostic piece - the piece is visible before 2028 // the trace is expanded. 2029 if (PDB.getGenerationScheme() != PathDiagnosticConsumer::None) { 2030 PathDiagnosticPiece *LastPiece = 0; 2031 for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end(); 2032 I != E; ++I) { 2033 if (PathDiagnosticPiece *Piece = (*I)->getEndPath(PDB, N, *R)) { 2034 assert (!LastPiece && 2035 "There can only be one final piece in a diagnostic."); 2036 LastPiece = Piece; 2037 } 2038 } 2039 if (!LastPiece) 2040 LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R); 2041 if (LastPiece) 2042 PD.setEndOfPath(LastPiece); 2043 else 2044 return false; 2045 } 2046 2047 switch (PDB.getGenerationScheme()) { 2048 case PathDiagnosticConsumer::Extensive: 2049 if (!GenerateExtensivePathDiagnostic(PD, PDB, N, visitors)) { 2050 assert(!R->isValid() && "Failed on valid report"); 2051 // Try again. We'll filter out the bad report when we trim the graph. 2052 // FIXME: It would be more efficient to use the same intermediate 2053 // trimmed graph, and just repeat the shortest-path search. 2054 return generatePathDiagnostic(PD, PC, bugReports); 2055 } 2056 break; 2057 case PathDiagnosticConsumer::Minimal: 2058 if (!GenerateMinimalPathDiagnostic(PD, PDB, N, visitors)) { 2059 assert(!R->isValid() && "Failed on valid report"); 2060 // Try again. We'll filter out the bad report when we trim the graph. 2061 return generatePathDiagnostic(PD, PC, bugReports); 2062 } 2063 break; 2064 case PathDiagnosticConsumer::None: 2065 if (!GenerateVisitorsOnlyPathDiagnostic(PD, PDB, N, visitors)) { 2066 assert(!R->isValid() && "Failed on valid report"); 2067 // Try again. We'll filter out the bad report when we trim the graph. 2068 return generatePathDiagnostic(PD, PC, bugReports); 2069 } 2070 break; 2071 } 2072 2073 // Clean up the visitors we used. 2074 llvm::DeleteContainerPointers(visitors); 2075 2076 // Did anything change while generating this path? 2077 finalReportConfigToken = R->getConfigurationChangeToken(); 2078 } while(finalReportConfigToken != originalReportConfigToken); 2079 2080 // Finally, prune the diagnostic path of uninteresting stuff. 2081 if (!PD.path.empty()) { 2082 // Remove messages that are basically the same. 2083 RemoveRedundantMsgs(PD.getMutablePieces()); 2084 2085 if (R->shouldPrunePath()) { 2086 bool hasSomethingInteresting = RemoveUneededCalls(PD.getMutablePieces(), 2087 R); 2088 assert(hasSomethingInteresting); 2089 (void) hasSomethingInteresting; 2090 } 2091 } 2092 2093 return true; 2094} 2095 2096void BugReporter::Register(BugType *BT) { 2097 BugTypes = F.add(BugTypes, BT); 2098} 2099 2100void BugReporter::EmitReport(BugReport* R) { 2101 // Compute the bug report's hash to determine its equivalence class. 2102 llvm::FoldingSetNodeID ID; 2103 R->Profile(ID); 2104 2105 // Lookup the equivance class. If there isn't one, create it. 2106 BugType& BT = R->getBugType(); 2107 Register(&BT); 2108 void *InsertPos; 2109 BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos); 2110 2111 if (!EQ) { 2112 EQ = new BugReportEquivClass(R); 2113 EQClasses.InsertNode(EQ, InsertPos); 2114 EQClassesVector.push_back(EQ); 2115 } 2116 else 2117 EQ->AddReport(R); 2118} 2119 2120 2121//===----------------------------------------------------------------------===// 2122// Emitting reports in equivalence classes. 2123//===----------------------------------------------------------------------===// 2124 2125namespace { 2126struct FRIEC_WLItem { 2127 const ExplodedNode *N; 2128 ExplodedNode::const_succ_iterator I, E; 2129 2130 FRIEC_WLItem(const ExplodedNode *n) 2131 : N(n), I(N->succ_begin()), E(N->succ_end()) {} 2132}; 2133} 2134 2135static BugReport * 2136FindReportInEquivalenceClass(BugReportEquivClass& EQ, 2137 SmallVectorImpl<BugReport*> &bugReports) { 2138 2139 BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end(); 2140 assert(I != E); 2141 BugType& BT = I->getBugType(); 2142 2143 // If we don't need to suppress any of the nodes because they are 2144 // post-dominated by a sink, simply add all the nodes in the equivalence class 2145 // to 'Nodes'. Any of the reports will serve as a "representative" report. 2146 if (!BT.isSuppressOnSink()) { 2147 BugReport *R = I; 2148 for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) { 2149 const ExplodedNode *N = I->getErrorNode(); 2150 if (N) { 2151 R = I; 2152 bugReports.push_back(R); 2153 } 2154 } 2155 return R; 2156 } 2157 2158 // For bug reports that should be suppressed when all paths are post-dominated 2159 // by a sink node, iterate through the reports in the equivalence class 2160 // until we find one that isn't post-dominated (if one exists). We use a 2161 // DFS traversal of the ExplodedGraph to find a non-sink node. We could write 2162 // this as a recursive function, but we don't want to risk blowing out the 2163 // stack for very long paths. 2164 BugReport *exampleReport = 0; 2165 2166 for (; I != E; ++I) { 2167 const ExplodedNode *errorNode = I->getErrorNode(); 2168 2169 if (!errorNode) 2170 continue; 2171 if (errorNode->isSink()) { 2172 llvm_unreachable( 2173 "BugType::isSuppressSink() should not be 'true' for sink end nodes"); 2174 } 2175 // No successors? By definition this nodes isn't post-dominated by a sink. 2176 if (errorNode->succ_empty()) { 2177 bugReports.push_back(I); 2178 if (!exampleReport) 2179 exampleReport = I; 2180 continue; 2181 } 2182 2183 // At this point we know that 'N' is not a sink and it has at least one 2184 // successor. Use a DFS worklist to find a non-sink end-of-path node. 2185 typedef FRIEC_WLItem WLItem; 2186 typedef SmallVector<WLItem, 10> DFSWorkList; 2187 llvm::DenseMap<const ExplodedNode *, unsigned> Visited; 2188 2189 DFSWorkList WL; 2190 WL.push_back(errorNode); 2191 Visited[errorNode] = 1; 2192 2193 while (!WL.empty()) { 2194 WLItem &WI = WL.back(); 2195 assert(!WI.N->succ_empty()); 2196 2197 for (; WI.I != WI.E; ++WI.I) { 2198 const ExplodedNode *Succ = *WI.I; 2199 // End-of-path node? 2200 if (Succ->succ_empty()) { 2201 // If we found an end-of-path node that is not a sink. 2202 if (!Succ->isSink()) { 2203 bugReports.push_back(I); 2204 if (!exampleReport) 2205 exampleReport = I; 2206 WL.clear(); 2207 break; 2208 } 2209 // Found a sink? Continue on to the next successor. 2210 continue; 2211 } 2212 // Mark the successor as visited. If it hasn't been explored, 2213 // enqueue it to the DFS worklist. 2214 unsigned &mark = Visited[Succ]; 2215 if (!mark) { 2216 mark = 1; 2217 WL.push_back(Succ); 2218 break; 2219 } 2220 } 2221 2222 // The worklist may have been cleared at this point. First 2223 // check if it is empty before checking the last item. 2224 if (!WL.empty() && &WL.back() == &WI) 2225 WL.pop_back(); 2226 } 2227 } 2228 2229 // ExampleReport will be NULL if all the nodes in the equivalence class 2230 // were post-dominated by sinks. 2231 return exampleReport; 2232} 2233 2234void BugReporter::FlushReport(BugReportEquivClass& EQ) { 2235 SmallVector<BugReport*, 10> bugReports; 2236 BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports); 2237 if (exampleReport) { 2238 const PathDiagnosticConsumers &C = getPathDiagnosticConsumers(); 2239 for (PathDiagnosticConsumers::const_iterator I=C.begin(), 2240 E=C.end(); I != E; ++I) { 2241 FlushReport(exampleReport, **I, bugReports); 2242 } 2243 } 2244} 2245 2246void BugReporter::FlushReport(BugReport *exampleReport, 2247 PathDiagnosticConsumer &PD, 2248 ArrayRef<BugReport*> bugReports) { 2249 2250 // FIXME: Make sure we use the 'R' for the path that was actually used. 2251 // Probably doesn't make a difference in practice. 2252 BugType& BT = exampleReport->getBugType(); 2253 2254 OwningPtr<PathDiagnostic> 2255 D(new PathDiagnostic(exampleReport->getDeclWithIssue(), 2256 exampleReport->getBugType().getName(), 2257 exampleReport->getDescription(), 2258 exampleReport->getShortDescription(/*Fallback=*/false), 2259 BT.getCategory())); 2260 2261 // Generate the full path diagnostic, using the generation scheme 2262 // specified by the PathDiagnosticConsumer. Note that we have to generate 2263 // path diagnostics even for consumers which do not support paths, because 2264 // the BugReporterVisitors may mark this bug as a false positive. 2265 if (!bugReports.empty()) 2266 if (!generatePathDiagnostic(*D.get(), PD, bugReports)) 2267 return; 2268 2269 // If the path is empty, generate a single step path with the location 2270 // of the issue. 2271 if (D->path.empty()) { 2272 PathDiagnosticLocation L = exampleReport->getLocation(getSourceManager()); 2273 PathDiagnosticPiece *piece = 2274 new PathDiagnosticEventPiece(L, exampleReport->getDescription()); 2275 BugReport::ranges_iterator Beg, End; 2276 llvm::tie(Beg, End) = exampleReport->getRanges(); 2277 for ( ; Beg != End; ++Beg) 2278 piece->addRange(*Beg); 2279 D->setEndOfPath(piece); 2280 } 2281 2282 // Get the meta data. 2283 const BugReport::ExtraTextList &Meta = exampleReport->getExtraText(); 2284 for (BugReport::ExtraTextList::const_iterator i = Meta.begin(), 2285 e = Meta.end(); i != e; ++i) { 2286 D->addMeta(*i); 2287 } 2288 2289 PD.HandlePathDiagnostic(D.take()); 2290} 2291 2292void BugReporter::EmitBasicReport(const Decl *DeclWithIssue, 2293 StringRef name, 2294 StringRef category, 2295 StringRef str, PathDiagnosticLocation Loc, 2296 SourceRange* RBeg, unsigned NumRanges) { 2297 2298 // 'BT' is owned by BugReporter. 2299 BugType *BT = getBugTypeForName(name, category); 2300 BugReport *R = new BugReport(*BT, str, Loc); 2301 R->setDeclWithIssue(DeclWithIssue); 2302 for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg); 2303 EmitReport(R); 2304} 2305 2306BugType *BugReporter::getBugTypeForName(StringRef name, 2307 StringRef category) { 2308 SmallString<136> fullDesc; 2309 llvm::raw_svector_ostream(fullDesc) << name << ":" << category; 2310 llvm::StringMapEntry<BugType *> & 2311 entry = StrBugTypes.GetOrCreateValue(fullDesc); 2312 BugType *BT = entry.getValue(); 2313 if (!BT) { 2314 BT = new BugType(name, category); 2315 entry.setValue(BT); 2316 } 2317 return BT; 2318} 2319