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