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