BugReporter.cpp revision a3f5a5afefca7653349a88472d5ce01ba7226e27
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/// A map from PathDiagnosticPiece to the LocationContext of the inlined 147/// function call it represents. 148typedef llvm::DenseMap<const PathPieces *, const LocationContext *> 149 LocationContextMap; 150 151/// Recursively scan through a path and prune out calls and macros pieces 152/// that aren't needed. Return true if afterwards the path contains 153/// "interesting stuff" which means it shouldn't be pruned from the parent path. 154static bool removeUnneededCalls(PathPieces &pieces, BugReport *R, 155 LocationContextMap &LCM) { 156 bool containsSomethingInteresting = false; 157 const unsigned N = pieces.size(); 158 159 for (unsigned i = 0 ; i < N ; ++i) { 160 // Remove the front piece from the path. If it is still something we 161 // want to keep once we are done, we will push it back on the end. 162 IntrusiveRefCntPtr<PathDiagnosticPiece> piece(pieces.front()); 163 pieces.pop_front(); 164 165 switch (piece->getKind()) { 166 case PathDiagnosticPiece::Call: { 167 PathDiagnosticCallPiece *call = cast<PathDiagnosticCallPiece>(piece); 168 // Check if the location context is interesting. 169 assert(LCM.count(&call->path)); 170 if (R->isInteresting(LCM[&call->path])) { 171 containsSomethingInteresting = true; 172 break; 173 } 174 175 if (!removeUnneededCalls(call->path, R, LCM)) 176 continue; 177 178 containsSomethingInteresting = true; 179 break; 180 } 181 case PathDiagnosticPiece::Macro: { 182 PathDiagnosticMacroPiece *macro = cast<PathDiagnosticMacroPiece>(piece); 183 if (!removeUnneededCalls(macro->subPieces, R, LCM)) 184 continue; 185 containsSomethingInteresting = true; 186 break; 187 } 188 case PathDiagnosticPiece::Event: { 189 PathDiagnosticEventPiece *event = cast<PathDiagnosticEventPiece>(piece); 190 191 // We never throw away an event, but we do throw it away wholesale 192 // as part of a path if we throw the entire path away. 193 containsSomethingInteresting |= !event->isPrunable(); 194 break; 195 } 196 case PathDiagnosticPiece::ControlFlow: 197 break; 198 } 199 200 pieces.push_back(piece); 201 } 202 203 return containsSomethingInteresting; 204} 205 206/// Returns true if the given decl has been implicitly given a body, either by 207/// the analyzer or by the compiler proper. 208static bool hasImplicitBody(const Decl *D) { 209 assert(D); 210 return D->isImplicit() || !D->hasBody(); 211} 212 213/// Recursively scan through a path and make sure that all call pieces have 214/// valid locations. 215static void adjustCallLocations(PathPieces &Pieces, 216 PathDiagnosticLocation *LastCallLocation = 0) { 217 for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E; ++I) { 218 PathDiagnosticCallPiece *Call = dyn_cast<PathDiagnosticCallPiece>(*I); 219 220 if (!Call) { 221 assert((*I)->getLocation().asLocation().isValid()); 222 continue; 223 } 224 225 if (LastCallLocation) { 226 bool CallerIsImplicit = hasImplicitBody(Call->getCaller()); 227 if (CallerIsImplicit || !Call->callEnter.asLocation().isValid()) 228 Call->callEnter = *LastCallLocation; 229 if (CallerIsImplicit || !Call->callReturn.asLocation().isValid()) 230 Call->callReturn = *LastCallLocation; 231 } 232 233 // Recursively clean out the subclass. Keep this call around if 234 // it contains any informative diagnostics. 235 PathDiagnosticLocation *ThisCallLocation; 236 if (Call->callEnterWithin.asLocation().isValid() && 237 !hasImplicitBody(Call->getCallee())) 238 ThisCallLocation = &Call->callEnterWithin; 239 else 240 ThisCallLocation = &Call->callEnter; 241 242 assert(ThisCallLocation && "Outermost call has an invalid location"); 243 adjustCallLocations(Call->path, ThisCallLocation); 244 } 245} 246 247/// Remove all pieces with invalid locations as these cannot be serialized. 248/// We might have pieces with invalid locations as a result of inlining Body 249/// Farm generated functions. 250static void removePiecesWithInvalidLocations(PathPieces &Pieces) { 251 for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) { 252 if (PathDiagnosticCallPiece *C = dyn_cast<PathDiagnosticCallPiece>(*I)) 253 removePiecesWithInvalidLocations(C->path); 254 255 if (PathDiagnosticMacroPiece *M = dyn_cast<PathDiagnosticMacroPiece>(*I)) 256 removePiecesWithInvalidLocations(M->subPieces); 257 258 if (!(*I)->getLocation().isValid() || 259 !(*I)->getLocation().asLocation().isValid()) { 260 I = Pieces.erase(I); 261 continue; 262 } 263 I++; 264 } 265} 266 267//===----------------------------------------------------------------------===// 268// PathDiagnosticBuilder and its associated routines and helper objects. 269//===----------------------------------------------------------------------===// 270 271namespace { 272class NodeMapClosure : public BugReport::NodeResolver { 273 InterExplodedGraphMap &M; 274public: 275 NodeMapClosure(InterExplodedGraphMap &m) : M(m) {} 276 277 const ExplodedNode *getOriginalNode(const ExplodedNode *N) { 278 return M.lookup(N); 279 } 280}; 281 282class PathDiagnosticBuilder : public BugReporterContext { 283 BugReport *R; 284 PathDiagnosticConsumer *PDC; 285 NodeMapClosure NMC; 286public: 287 const LocationContext *LC; 288 289 PathDiagnosticBuilder(GRBugReporter &br, 290 BugReport *r, InterExplodedGraphMap &Backmap, 291 PathDiagnosticConsumer *pdc) 292 : BugReporterContext(br), 293 R(r), PDC(pdc), NMC(Backmap), LC(r->getErrorNode()->getLocationContext()) 294 {} 295 296 PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N); 297 298 PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os, 299 const ExplodedNode *N); 300 301 BugReport *getBugReport() { return R; } 302 303 Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); } 304 305 ParentMap& getParentMap() { return LC->getParentMap(); } 306 307 const Stmt *getParent(const Stmt *S) { 308 return getParentMap().getParent(S); 309 } 310 311 virtual NodeMapClosure& getNodeResolver() { return NMC; } 312 313 PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S); 314 315 PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const { 316 return PDC ? PDC->getGenerationScheme() : PathDiagnosticConsumer::Extensive; 317 } 318 319 bool supportsLogicalOpControlFlow() const { 320 return PDC ? PDC->supportsLogicalOpControlFlow() : true; 321 } 322}; 323} // end anonymous namespace 324 325PathDiagnosticLocation 326PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) { 327 if (const Stmt *S = PathDiagnosticLocation::getNextStmt(N)) 328 return PathDiagnosticLocation(S, getSourceManager(), LC); 329 330 return PathDiagnosticLocation::createDeclEnd(N->getLocationContext(), 331 getSourceManager()); 332} 333 334PathDiagnosticLocation 335PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os, 336 const ExplodedNode *N) { 337 338 // Slow, but probably doesn't matter. 339 if (os.str().empty()) 340 os << ' '; 341 342 const PathDiagnosticLocation &Loc = ExecutionContinues(N); 343 344 if (Loc.asStmt()) 345 os << "Execution continues on line " 346 << getSourceManager().getExpansionLineNumber(Loc.asLocation()) 347 << '.'; 348 else { 349 os << "Execution jumps to the end of the "; 350 const Decl *D = N->getLocationContext()->getDecl(); 351 if (isa<ObjCMethodDecl>(D)) 352 os << "method"; 353 else if (isa<FunctionDecl>(D)) 354 os << "function"; 355 else { 356 assert(isa<BlockDecl>(D)); 357 os << "anonymous block"; 358 } 359 os << '.'; 360 } 361 362 return Loc; 363} 364 365static const Stmt *getEnclosingParent(const Stmt *S, const ParentMap &PM) { 366 if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S))) 367 return PM.getParentIgnoreParens(S); 368 369 const Stmt *Parent = PM.getParentIgnoreParens(S); 370 if (!Parent) 371 return 0; 372 373 switch (Parent->getStmtClass()) { 374 case Stmt::ForStmtClass: 375 case Stmt::DoStmtClass: 376 case Stmt::WhileStmtClass: 377 case Stmt::ObjCForCollectionStmtClass: 378 case Stmt::CXXForRangeStmtClass: 379 return Parent; 380 default: 381 break; 382 } 383 384 return 0; 385} 386 387static PathDiagnosticLocation 388getEnclosingStmtLocation(const Stmt *S, SourceManager &SMgr, const ParentMap &P, 389 const LocationContext *LC, bool allowNestedContexts) { 390 if (!S) 391 return PathDiagnosticLocation(); 392 393 while (const Stmt *Parent = getEnclosingParent(S, P)) { 394 switch (Parent->getStmtClass()) { 395 case Stmt::BinaryOperatorClass: { 396 const BinaryOperator *B = cast<BinaryOperator>(Parent); 397 if (B->isLogicalOp()) 398 return PathDiagnosticLocation(allowNestedContexts ? B : S, SMgr, LC); 399 break; 400 } 401 case Stmt::CompoundStmtClass: 402 case Stmt::StmtExprClass: 403 return PathDiagnosticLocation(S, SMgr, LC); 404 case Stmt::ChooseExprClass: 405 // Similar to '?' if we are referring to condition, just have the edge 406 // point to the entire choose expression. 407 if (allowNestedContexts || cast<ChooseExpr>(Parent)->getCond() == S) 408 return PathDiagnosticLocation(Parent, SMgr, LC); 409 else 410 return PathDiagnosticLocation(S, SMgr, LC); 411 case Stmt::BinaryConditionalOperatorClass: 412 case Stmt::ConditionalOperatorClass: 413 // For '?', if we are referring to condition, just have the edge point 414 // to the entire '?' expression. 415 if (allowNestedContexts || 416 cast<AbstractConditionalOperator>(Parent)->getCond() == S) 417 return PathDiagnosticLocation(Parent, SMgr, LC); 418 else 419 return PathDiagnosticLocation(S, SMgr, LC); 420 case Stmt::CXXForRangeStmtClass: 421 if (cast<CXXForRangeStmt>(Parent)->getBody() == S) 422 return PathDiagnosticLocation(S, SMgr, LC); 423 break; 424 case Stmt::DoStmtClass: 425 return PathDiagnosticLocation(S, SMgr, LC); 426 case Stmt::ForStmtClass: 427 if (cast<ForStmt>(Parent)->getBody() == S) 428 return PathDiagnosticLocation(S, SMgr, LC); 429 break; 430 case Stmt::IfStmtClass: 431 if (cast<IfStmt>(Parent)->getCond() != S) 432 return PathDiagnosticLocation(S, SMgr, LC); 433 break; 434 case Stmt::ObjCForCollectionStmtClass: 435 if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S) 436 return PathDiagnosticLocation(S, SMgr, LC); 437 break; 438 case Stmt::WhileStmtClass: 439 if (cast<WhileStmt>(Parent)->getCond() != S) 440 return PathDiagnosticLocation(S, SMgr, LC); 441 break; 442 default: 443 break; 444 } 445 446 S = Parent; 447 } 448 449 assert(S && "Cannot have null Stmt for PathDiagnosticLocation"); 450 451 return PathDiagnosticLocation(S, SMgr, LC); 452} 453 454PathDiagnosticLocation 455PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { 456 assert(S && "Null Stmt passed to getEnclosingStmtLocation"); 457 return ::getEnclosingStmtLocation(S, getSourceManager(), getParentMap(), LC, 458 /*allowNestedContexts=*/false); 459} 460 461//===----------------------------------------------------------------------===// 462// "Visitors only" path diagnostic generation algorithm. 463//===----------------------------------------------------------------------===// 464static bool GenerateVisitorsOnlyPathDiagnostic(PathDiagnostic &PD, 465 PathDiagnosticBuilder &PDB, 466 const ExplodedNode *N, 467 ArrayRef<BugReporterVisitor *> visitors) { 468 // All path generation skips the very first node (the error node). 469 // This is because there is special handling for the end-of-path note. 470 N = N->getFirstPred(); 471 if (!N) 472 return true; 473 474 BugReport *R = PDB.getBugReport(); 475 while (const ExplodedNode *Pred = N->getFirstPred()) { 476 for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(), 477 E = visitors.end(); 478 I != E; ++I) { 479 // Visit all the node pairs, but throw the path pieces away. 480 PathDiagnosticPiece *Piece = (*I)->VisitNode(N, Pred, PDB, *R); 481 delete Piece; 482 } 483 484 N = Pred; 485 } 486 487 return R->isValid(); 488} 489 490//===----------------------------------------------------------------------===// 491// "Minimal" path diagnostic generation algorithm. 492//===----------------------------------------------------------------------===// 493typedef std::pair<PathDiagnosticCallPiece*, const ExplodedNode*> StackDiagPair; 494typedef SmallVector<StackDiagPair, 6> StackDiagVector; 495 496static void updateStackPiecesWithMessage(PathDiagnosticPiece *P, 497 StackDiagVector &CallStack) { 498 // If the piece contains a special message, add it to all the call 499 // pieces on the active stack. 500 if (PathDiagnosticEventPiece *ep = 501 dyn_cast<PathDiagnosticEventPiece>(P)) { 502 503 if (ep->hasCallStackHint()) 504 for (StackDiagVector::iterator I = CallStack.begin(), 505 E = CallStack.end(); I != E; ++I) { 506 PathDiagnosticCallPiece *CP = I->first; 507 const ExplodedNode *N = I->second; 508 std::string stackMsg = ep->getCallStackMessage(N); 509 510 // The last message on the path to final bug is the most important 511 // one. Since we traverse the path backwards, do not add the message 512 // if one has been previously added. 513 if (!CP->hasCallStackMessage()) 514 CP->setCallStackMessage(stackMsg); 515 } 516 } 517} 518 519static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM); 520 521static bool GenerateMinimalPathDiagnostic(PathDiagnostic& PD, 522 PathDiagnosticBuilder &PDB, 523 const ExplodedNode *N, 524 LocationContextMap &LCM, 525 ArrayRef<BugReporterVisitor *> visitors) { 526 527 SourceManager& SMgr = PDB.getSourceManager(); 528 const LocationContext *LC = PDB.LC; 529 const ExplodedNode *NextNode = N->pred_empty() 530 ? NULL : *(N->pred_begin()); 531 532 StackDiagVector CallStack; 533 534 while (NextNode) { 535 N = NextNode; 536 PDB.LC = N->getLocationContext(); 537 NextNode = N->getFirstPred(); 538 539 ProgramPoint P = N->getLocation(); 540 541 do { 542 if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) { 543 PathDiagnosticCallPiece *C = 544 PathDiagnosticCallPiece::construct(N, *CE, SMgr); 545 // Record the mapping from call piece to LocationContext. 546 LCM[&C->path] = CE->getCalleeContext(); 547 PD.getActivePath().push_front(C); 548 PD.pushActivePath(&C->path); 549 CallStack.push_back(StackDiagPair(C, N)); 550 break; 551 } 552 553 if (Optional<CallEnter> CE = P.getAs<CallEnter>()) { 554 // Flush all locations, and pop the active path. 555 bool VisitedEntireCall = PD.isWithinCall(); 556 PD.popActivePath(); 557 558 // Either we just added a bunch of stuff to the top-level path, or 559 // we have a previous CallExitEnd. If the former, it means that the 560 // path terminated within a function call. We must then take the 561 // current contents of the active path and place it within 562 // a new PathDiagnosticCallPiece. 563 PathDiagnosticCallPiece *C; 564 if (VisitedEntireCall) { 565 C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); 566 } else { 567 const Decl *Caller = CE->getLocationContext()->getDecl(); 568 C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 569 // Record the mapping from call piece to LocationContext. 570 LCM[&C->path] = CE->getCalleeContext(); 571 } 572 573 C->setCallee(*CE, SMgr); 574 if (!CallStack.empty()) { 575 assert(CallStack.back().first == C); 576 CallStack.pop_back(); 577 } 578 break; 579 } 580 581 if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) { 582 const CFGBlock *Src = BE->getSrc(); 583 const CFGBlock *Dst = BE->getDst(); 584 const Stmt *T = Src->getTerminator(); 585 586 if (!T) 587 break; 588 589 PathDiagnosticLocation Start = 590 PathDiagnosticLocation::createBegin(T, SMgr, 591 N->getLocationContext()); 592 593 switch (T->getStmtClass()) { 594 default: 595 break; 596 597 case Stmt::GotoStmtClass: 598 case Stmt::IndirectGotoStmtClass: { 599 const Stmt *S = PathDiagnosticLocation::getNextStmt(N); 600 601 if (!S) 602 break; 603 604 std::string sbuf; 605 llvm::raw_string_ostream os(sbuf); 606 const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S); 607 608 os << "Control jumps to line " 609 << End.asLocation().getExpansionLineNumber(); 610 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 611 Start, End, os.str())); 612 break; 613 } 614 615 case Stmt::SwitchStmtClass: { 616 // Figure out what case arm we took. 617 std::string sbuf; 618 llvm::raw_string_ostream os(sbuf); 619 620 if (const Stmt *S = Dst->getLabel()) { 621 PathDiagnosticLocation End(S, SMgr, LC); 622 623 switch (S->getStmtClass()) { 624 default: 625 os << "No cases match in the switch statement. " 626 "Control jumps to line " 627 << End.asLocation().getExpansionLineNumber(); 628 break; 629 case Stmt::DefaultStmtClass: 630 os << "Control jumps to the 'default' case at line " 631 << End.asLocation().getExpansionLineNumber(); 632 break; 633 634 case Stmt::CaseStmtClass: { 635 os << "Control jumps to 'case "; 636 const CaseStmt *Case = cast<CaseStmt>(S); 637 const Expr *LHS = Case->getLHS()->IgnoreParenCasts(); 638 639 // Determine if it is an enum. 640 bool GetRawInt = true; 641 642 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) { 643 // FIXME: Maybe this should be an assertion. Are there cases 644 // were it is not an EnumConstantDecl? 645 const EnumConstantDecl *D = 646 dyn_cast<EnumConstantDecl>(DR->getDecl()); 647 648 if (D) { 649 GetRawInt = false; 650 os << *D; 651 } 652 } 653 654 if (GetRawInt) 655 os << LHS->EvaluateKnownConstInt(PDB.getASTContext()); 656 657 os << ":' at line " 658 << End.asLocation().getExpansionLineNumber(); 659 break; 660 } 661 } 662 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 663 Start, End, os.str())); 664 } 665 else { 666 os << "'Default' branch taken. "; 667 const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N); 668 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 669 Start, End, os.str())); 670 } 671 672 break; 673 } 674 675 case Stmt::BreakStmtClass: 676 case Stmt::ContinueStmtClass: { 677 std::string sbuf; 678 llvm::raw_string_ostream os(sbuf); 679 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 680 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 681 Start, End, os.str())); 682 break; 683 } 684 685 // Determine control-flow for ternary '?'. 686 case Stmt::BinaryConditionalOperatorClass: 687 case Stmt::ConditionalOperatorClass: { 688 std::string sbuf; 689 llvm::raw_string_ostream os(sbuf); 690 os << "'?' condition is "; 691 692 if (*(Src->succ_begin()+1) == Dst) 693 os << "false"; 694 else 695 os << "true"; 696 697 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 698 699 if (const Stmt *S = End.asStmt()) 700 End = PDB.getEnclosingStmtLocation(S); 701 702 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 703 Start, End, os.str())); 704 break; 705 } 706 707 // Determine control-flow for short-circuited '&&' and '||'. 708 case Stmt::BinaryOperatorClass: { 709 if (!PDB.supportsLogicalOpControlFlow()) 710 break; 711 712 const BinaryOperator *B = cast<BinaryOperator>(T); 713 std::string sbuf; 714 llvm::raw_string_ostream os(sbuf); 715 os << "Left side of '"; 716 717 if (B->getOpcode() == BO_LAnd) { 718 os << "&&" << "' is "; 719 720 if (*(Src->succ_begin()+1) == Dst) { 721 os << "false"; 722 PathDiagnosticLocation End(B->getLHS(), SMgr, LC); 723 PathDiagnosticLocation Start = 724 PathDiagnosticLocation::createOperatorLoc(B, SMgr); 725 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 726 Start, End, os.str())); 727 } 728 else { 729 os << "true"; 730 PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); 731 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 732 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 733 Start, End, os.str())); 734 } 735 } 736 else { 737 assert(B->getOpcode() == BO_LOr); 738 os << "||" << "' is "; 739 740 if (*(Src->succ_begin()+1) == Dst) { 741 os << "false"; 742 PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); 743 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 744 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 745 Start, End, os.str())); 746 } 747 else { 748 os << "true"; 749 PathDiagnosticLocation End(B->getLHS(), SMgr, LC); 750 PathDiagnosticLocation Start = 751 PathDiagnosticLocation::createOperatorLoc(B, SMgr); 752 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 753 Start, End, os.str())); 754 } 755 } 756 757 break; 758 } 759 760 case Stmt::DoStmtClass: { 761 if (*(Src->succ_begin()) == Dst) { 762 std::string sbuf; 763 llvm::raw_string_ostream os(sbuf); 764 765 os << "Loop condition is true. "; 766 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 767 768 if (const Stmt *S = End.asStmt()) 769 End = PDB.getEnclosingStmtLocation(S); 770 771 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 772 Start, End, os.str())); 773 } 774 else { 775 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 776 777 if (const Stmt *S = End.asStmt()) 778 End = PDB.getEnclosingStmtLocation(S); 779 780 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 781 Start, End, "Loop condition is false. Exiting loop")); 782 } 783 784 break; 785 } 786 787 case Stmt::WhileStmtClass: 788 case Stmt::ForStmtClass: { 789 if (*(Src->succ_begin()+1) == Dst) { 790 std::string sbuf; 791 llvm::raw_string_ostream os(sbuf); 792 793 os << "Loop condition is false. "; 794 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 795 if (const Stmt *S = End.asStmt()) 796 End = PDB.getEnclosingStmtLocation(S); 797 798 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 799 Start, End, os.str())); 800 } 801 else { 802 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 803 if (const Stmt *S = End.asStmt()) 804 End = PDB.getEnclosingStmtLocation(S); 805 806 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 807 Start, End, "Loop condition is true. Entering loop body")); 808 } 809 810 break; 811 } 812 813 case Stmt::IfStmtClass: { 814 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 815 816 if (const Stmt *S = End.asStmt()) 817 End = PDB.getEnclosingStmtLocation(S); 818 819 if (*(Src->succ_begin()+1) == Dst) 820 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 821 Start, End, "Taking false branch")); 822 else 823 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 824 Start, End, "Taking true branch")); 825 826 break; 827 } 828 } 829 } 830 } while(0); 831 832 if (NextNode) { 833 // Add diagnostic pieces from custom visitors. 834 BugReport *R = PDB.getBugReport(); 835 for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(), 836 E = visitors.end(); 837 I != E; ++I) { 838 if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) { 839 PD.getActivePath().push_front(p); 840 updateStackPiecesWithMessage(p, CallStack); 841 } 842 } 843 } 844 } 845 846 if (!PDB.getBugReport()->isValid()) 847 return false; 848 849 // After constructing the full PathDiagnostic, do a pass over it to compact 850 // PathDiagnosticPieces that occur within a macro. 851 CompactPathDiagnostic(PD.getMutablePieces(), PDB.getSourceManager()); 852 return true; 853} 854 855//===----------------------------------------------------------------------===// 856// "Extensive" PathDiagnostic generation. 857//===----------------------------------------------------------------------===// 858 859static bool IsControlFlowExpr(const Stmt *S) { 860 const Expr *E = dyn_cast<Expr>(S); 861 862 if (!E) 863 return false; 864 865 E = E->IgnoreParenCasts(); 866 867 if (isa<AbstractConditionalOperator>(E)) 868 return true; 869 870 if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E)) 871 if (B->isLogicalOp()) 872 return true; 873 874 return false; 875} 876 877namespace { 878class ContextLocation : public PathDiagnosticLocation { 879 bool IsDead; 880public: 881 ContextLocation(const PathDiagnosticLocation &L, bool isdead = false) 882 : PathDiagnosticLocation(L), IsDead(isdead) {} 883 884 void markDead() { IsDead = true; } 885 bool isDead() const { return IsDead; } 886}; 887 888static PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L, 889 const LocationContext *LC, 890 bool firstCharOnly = false) { 891 if (const Stmt *S = L.asStmt()) { 892 const Stmt *Original = S; 893 while (1) { 894 // Adjust the location for some expressions that are best referenced 895 // by one of their subexpressions. 896 switch (S->getStmtClass()) { 897 default: 898 break; 899 case Stmt::ParenExprClass: 900 case Stmt::GenericSelectionExprClass: 901 S = cast<Expr>(S)->IgnoreParens(); 902 firstCharOnly = true; 903 continue; 904 case Stmt::BinaryConditionalOperatorClass: 905 case Stmt::ConditionalOperatorClass: 906 S = cast<AbstractConditionalOperator>(S)->getCond(); 907 firstCharOnly = true; 908 continue; 909 case Stmt::ChooseExprClass: 910 S = cast<ChooseExpr>(S)->getCond(); 911 firstCharOnly = true; 912 continue; 913 case Stmt::BinaryOperatorClass: 914 S = cast<BinaryOperator>(S)->getLHS(); 915 firstCharOnly = true; 916 continue; 917 } 918 919 break; 920 } 921 922 if (S != Original) 923 L = PathDiagnosticLocation(S, L.getManager(), LC); 924 } 925 926 if (firstCharOnly) 927 L = PathDiagnosticLocation::createSingleLocation(L); 928 929 return L; 930} 931 932class EdgeBuilder { 933 std::vector<ContextLocation> CLocs; 934 typedef std::vector<ContextLocation>::iterator iterator; 935 PathDiagnostic &PD; 936 PathDiagnosticBuilder &PDB; 937 PathDiagnosticLocation PrevLoc; 938 939 bool IsConsumedExpr(const PathDiagnosticLocation &L); 940 941 bool containsLocation(const PathDiagnosticLocation &Container, 942 const PathDiagnosticLocation &Containee); 943 944 PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L); 945 946 947 948 void popLocation() { 949 if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) { 950 // For contexts, we only one the first character as the range. 951 rawAddEdge(cleanUpLocation(CLocs.back(), PDB.LC, true)); 952 } 953 CLocs.pop_back(); 954 } 955 956public: 957 EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb) 958 : PD(pd), PDB(pdb) { 959 960 // If the PathDiagnostic already has pieces, add the enclosing statement 961 // of the first piece as a context as well. 962 if (!PD.path.empty()) { 963 PrevLoc = (*PD.path.begin())->getLocation(); 964 965 if (const Stmt *S = PrevLoc.asStmt()) 966 addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 967 } 968 } 969 970 ~EdgeBuilder() { 971 while (!CLocs.empty()) popLocation(); 972 973 // Finally, add an initial edge from the start location of the first 974 // statement (if it doesn't already exist). 975 PathDiagnosticLocation L = PathDiagnosticLocation::createDeclBegin( 976 PDB.LC, 977 PDB.getSourceManager()); 978 if (L.isValid()) 979 rawAddEdge(L); 980 } 981 982 void flushLocations() { 983 while (!CLocs.empty()) 984 popLocation(); 985 PrevLoc = PathDiagnosticLocation(); 986 } 987 988 void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false, 989 bool IsPostJump = false); 990 991 void rawAddEdge(PathDiagnosticLocation NewLoc); 992 993 void addContext(const Stmt *S); 994 void addContext(const PathDiagnosticLocation &L); 995 void addExtendedContext(const Stmt *S); 996}; 997} // end anonymous namespace 998 999 1000PathDiagnosticLocation 1001EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) { 1002 if (const Stmt *S = L.asStmt()) { 1003 if (IsControlFlowExpr(S)) 1004 return L; 1005 1006 return PDB.getEnclosingStmtLocation(S); 1007 } 1008 1009 return L; 1010} 1011 1012bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container, 1013 const PathDiagnosticLocation &Containee) { 1014 1015 if (Container == Containee) 1016 return true; 1017 1018 if (Container.asDecl()) 1019 return true; 1020 1021 if (const Stmt *S = Containee.asStmt()) 1022 if (const Stmt *ContainerS = Container.asStmt()) { 1023 while (S) { 1024 if (S == ContainerS) 1025 return true; 1026 S = PDB.getParent(S); 1027 } 1028 return false; 1029 } 1030 1031 // Less accurate: compare using source ranges. 1032 SourceRange ContainerR = Container.asRange(); 1033 SourceRange ContaineeR = Containee.asRange(); 1034 1035 SourceManager &SM = PDB.getSourceManager(); 1036 SourceLocation ContainerRBeg = SM.getExpansionLoc(ContainerR.getBegin()); 1037 SourceLocation ContainerREnd = SM.getExpansionLoc(ContainerR.getEnd()); 1038 SourceLocation ContaineeRBeg = SM.getExpansionLoc(ContaineeR.getBegin()); 1039 SourceLocation ContaineeREnd = SM.getExpansionLoc(ContaineeR.getEnd()); 1040 1041 unsigned ContainerBegLine = SM.getExpansionLineNumber(ContainerRBeg); 1042 unsigned ContainerEndLine = SM.getExpansionLineNumber(ContainerREnd); 1043 unsigned ContaineeBegLine = SM.getExpansionLineNumber(ContaineeRBeg); 1044 unsigned ContaineeEndLine = SM.getExpansionLineNumber(ContaineeREnd); 1045 1046 assert(ContainerBegLine <= ContainerEndLine); 1047 assert(ContaineeBegLine <= ContaineeEndLine); 1048 1049 return (ContainerBegLine <= ContaineeBegLine && 1050 ContainerEndLine >= ContaineeEndLine && 1051 (ContainerBegLine != ContaineeBegLine || 1052 SM.getExpansionColumnNumber(ContainerRBeg) <= 1053 SM.getExpansionColumnNumber(ContaineeRBeg)) && 1054 (ContainerEndLine != ContaineeEndLine || 1055 SM.getExpansionColumnNumber(ContainerREnd) >= 1056 SM.getExpansionColumnNumber(ContaineeREnd))); 1057} 1058 1059void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) { 1060 if (!PrevLoc.isValid()) { 1061 PrevLoc = NewLoc; 1062 return; 1063 } 1064 1065 const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc, PDB.LC); 1066 const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc, PDB.LC); 1067 1068 if (PrevLocClean.asLocation().isInvalid()) { 1069 PrevLoc = NewLoc; 1070 return; 1071 } 1072 1073 if (NewLocClean.asLocation() == PrevLocClean.asLocation()) 1074 return; 1075 1076 // FIXME: Ignore intra-macro edges for now. 1077 if (NewLocClean.asLocation().getExpansionLoc() == 1078 PrevLocClean.asLocation().getExpansionLoc()) 1079 return; 1080 1081 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean)); 1082 PrevLoc = NewLoc; 1083} 1084 1085void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd, 1086 bool IsPostJump) { 1087 1088 if (!alwaysAdd && NewLoc.asLocation().isMacroID()) 1089 return; 1090 1091 const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc); 1092 1093 while (!CLocs.empty()) { 1094 ContextLocation &TopContextLoc = CLocs.back(); 1095 1096 // Is the top location context the same as the one for the new location? 1097 if (TopContextLoc == CLoc) { 1098 if (alwaysAdd) { 1099 if (IsConsumedExpr(TopContextLoc)) 1100 TopContextLoc.markDead(); 1101 1102 rawAddEdge(NewLoc); 1103 } 1104 1105 if (IsPostJump) 1106 TopContextLoc.markDead(); 1107 return; 1108 } 1109 1110 if (containsLocation(TopContextLoc, CLoc)) { 1111 if (alwaysAdd) { 1112 rawAddEdge(NewLoc); 1113 1114 if (IsConsumedExpr(CLoc)) { 1115 CLocs.push_back(ContextLocation(CLoc, /*IsDead=*/true)); 1116 return; 1117 } 1118 } 1119 1120 CLocs.push_back(ContextLocation(CLoc, /*IsDead=*/IsPostJump)); 1121 return; 1122 } 1123 1124 // Context does not contain the location. Flush it. 1125 popLocation(); 1126 } 1127 1128 // If we reach here, there is no enclosing context. Just add the edge. 1129 rawAddEdge(NewLoc); 1130} 1131 1132bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) { 1133 if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt())) 1134 return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X); 1135 1136 return false; 1137} 1138 1139void EdgeBuilder::addExtendedContext(const Stmt *S) { 1140 if (!S) 1141 return; 1142 1143 const Stmt *Parent = PDB.getParent(S); 1144 while (Parent) { 1145 if (isa<CompoundStmt>(Parent)) 1146 Parent = PDB.getParent(Parent); 1147 else 1148 break; 1149 } 1150 1151 if (Parent) { 1152 switch (Parent->getStmtClass()) { 1153 case Stmt::DoStmtClass: 1154 case Stmt::ObjCAtSynchronizedStmtClass: 1155 addContext(Parent); 1156 default: 1157 break; 1158 } 1159 } 1160 1161 addContext(S); 1162} 1163 1164void EdgeBuilder::addContext(const Stmt *S) { 1165 if (!S) 1166 return; 1167 1168 PathDiagnosticLocation L(S, PDB.getSourceManager(), PDB.LC); 1169 addContext(L); 1170} 1171 1172void EdgeBuilder::addContext(const PathDiagnosticLocation &L) { 1173 while (!CLocs.empty()) { 1174 const PathDiagnosticLocation &TopContextLoc = CLocs.back(); 1175 1176 // Is the top location context the same as the one for the new location? 1177 if (TopContextLoc == L) 1178 return; 1179 1180 if (containsLocation(TopContextLoc, L)) { 1181 CLocs.push_back(L); 1182 return; 1183 } 1184 1185 // Context does not contain the location. Flush it. 1186 popLocation(); 1187 } 1188 1189 CLocs.push_back(L); 1190} 1191 1192// Cone-of-influence: support the reverse propagation of "interesting" symbols 1193// and values by tracing interesting calculations backwards through evaluated 1194// expressions along a path. This is probably overly complicated, but the idea 1195// is that if an expression computed an "interesting" value, the child 1196// expressions are are also likely to be "interesting" as well (which then 1197// propagates to the values they in turn compute). This reverse propagation 1198// is needed to track interesting correlations across function call boundaries, 1199// where formal arguments bind to actual arguments, etc. This is also needed 1200// because the constraint solver sometimes simplifies certain symbolic values 1201// into constants when appropriate, and this complicates reasoning about 1202// interesting values. 1203typedef llvm::DenseSet<const Expr *> InterestingExprs; 1204 1205static void reversePropagateIntererstingSymbols(BugReport &R, 1206 InterestingExprs &IE, 1207 const ProgramState *State, 1208 const Expr *Ex, 1209 const LocationContext *LCtx) { 1210 SVal V = State->getSVal(Ex, LCtx); 1211 if (!(R.isInteresting(V) || IE.count(Ex))) 1212 return; 1213 1214 switch (Ex->getStmtClass()) { 1215 default: 1216 if (!isa<CastExpr>(Ex)) 1217 break; 1218 // Fall through. 1219 case Stmt::BinaryOperatorClass: 1220 case Stmt::UnaryOperatorClass: { 1221 for (Stmt::const_child_iterator CI = Ex->child_begin(), 1222 CE = Ex->child_end(); 1223 CI != CE; ++CI) { 1224 if (const Expr *child = dyn_cast_or_null<Expr>(*CI)) { 1225 IE.insert(child); 1226 SVal ChildV = State->getSVal(child, LCtx); 1227 R.markInteresting(ChildV); 1228 } 1229 break; 1230 } 1231 } 1232 } 1233 1234 R.markInteresting(V); 1235} 1236 1237static void reversePropagateInterestingSymbols(BugReport &R, 1238 InterestingExprs &IE, 1239 const ProgramState *State, 1240 const LocationContext *CalleeCtx, 1241 const LocationContext *CallerCtx) 1242{ 1243 // FIXME: Handle non-CallExpr-based CallEvents. 1244 const StackFrameContext *Callee = CalleeCtx->getCurrentStackFrame(); 1245 const Stmt *CallSite = Callee->getCallSite(); 1246 if (const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite)) { 1247 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CalleeCtx->getDecl())) { 1248 FunctionDecl::param_const_iterator PI = FD->param_begin(), 1249 PE = FD->param_end(); 1250 CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end(); 1251 for (; AI != AE && PI != PE; ++AI, ++PI) { 1252 if (const Expr *ArgE = *AI) { 1253 if (const ParmVarDecl *PD = *PI) { 1254 Loc LV = State->getLValue(PD, CalleeCtx); 1255 if (R.isInteresting(LV) || R.isInteresting(State->getRawSVal(LV))) 1256 IE.insert(ArgE); 1257 } 1258 } 1259 } 1260 } 1261 } 1262} 1263 1264//===----------------------------------------------------------------------===// 1265// Functions for determining if a loop was executed 0 times. 1266//===----------------------------------------------------------------------===// 1267 1268static bool isLoop(const Stmt *Term) { 1269 switch (Term->getStmtClass()) { 1270 case Stmt::ForStmtClass: 1271 case Stmt::WhileStmtClass: 1272 case Stmt::ObjCForCollectionStmtClass: 1273 case Stmt::CXXForRangeStmtClass: 1274 return true; 1275 default: 1276 // Note that we intentionally do not include do..while here. 1277 return false; 1278 } 1279} 1280 1281static bool isJumpToFalseBranch(const BlockEdge *BE) { 1282 const CFGBlock *Src = BE->getSrc(); 1283 assert(Src->succ_size() == 2); 1284 return (*(Src->succ_begin()+1) == BE->getDst()); 1285} 1286 1287/// Return true if the terminator is a loop and the destination is the 1288/// false branch. 1289static bool isLoopJumpPastBody(const Stmt *Term, const BlockEdge *BE) { 1290 if (!isLoop(Term)) 1291 return false; 1292 1293 // Did we take the false branch? 1294 return isJumpToFalseBranch(BE); 1295} 1296 1297static bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS) { 1298 while (SubS) { 1299 if (SubS == S) 1300 return true; 1301 SubS = PM.getParent(SubS); 1302 } 1303 return false; 1304} 1305 1306static const Stmt *getStmtBeforeCond(ParentMap &PM, const Stmt *Term, 1307 const ExplodedNode *N) { 1308 while (N) { 1309 Optional<StmtPoint> SP = N->getLocation().getAs<StmtPoint>(); 1310 if (SP) { 1311 const Stmt *S = SP->getStmt(); 1312 if (!isContainedByStmt(PM, Term, S)) 1313 return S; 1314 } 1315 N = N->getFirstPred(); 1316 } 1317 return 0; 1318} 1319 1320static bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term) { 1321 const Stmt *LoopBody = 0; 1322 switch (Term->getStmtClass()) { 1323 case Stmt::CXXForRangeStmtClass: { 1324 const CXXForRangeStmt *FR = cast<CXXForRangeStmt>(Term); 1325 if (isContainedByStmt(PM, FR->getInc(), S)) 1326 return true; 1327 if (isContainedByStmt(PM, FR->getLoopVarStmt(), S)) 1328 return true; 1329 LoopBody = FR->getBody(); 1330 break; 1331 } 1332 case Stmt::ForStmtClass: { 1333 const ForStmt *FS = cast<ForStmt>(Term); 1334 if (isContainedByStmt(PM, FS->getInc(), S)) 1335 return true; 1336 LoopBody = FS->getBody(); 1337 break; 1338 } 1339 case Stmt::ObjCForCollectionStmtClass: { 1340 const ObjCForCollectionStmt *FC = cast<ObjCForCollectionStmt>(Term); 1341 LoopBody = FC->getBody(); 1342 break; 1343 } 1344 case Stmt::WhileStmtClass: 1345 LoopBody = cast<WhileStmt>(Term)->getBody(); 1346 break; 1347 default: 1348 return false; 1349 } 1350 return isContainedByStmt(PM, LoopBody, S); 1351} 1352 1353//===----------------------------------------------------------------------===// 1354// Top-level logic for generating extensive path diagnostics. 1355//===----------------------------------------------------------------------===// 1356 1357static bool GenerateExtensivePathDiagnostic(PathDiagnostic& PD, 1358 PathDiagnosticBuilder &PDB, 1359 const ExplodedNode *N, 1360 LocationContextMap &LCM, 1361 ArrayRef<BugReporterVisitor *> visitors) { 1362 EdgeBuilder EB(PD, PDB); 1363 const SourceManager& SM = PDB.getSourceManager(); 1364 StackDiagVector CallStack; 1365 InterestingExprs IE; 1366 1367 const ExplodedNode *NextNode = N->pred_empty() ? NULL : *(N->pred_begin()); 1368 while (NextNode) { 1369 N = NextNode; 1370 NextNode = N->getFirstPred(); 1371 ProgramPoint P = N->getLocation(); 1372 1373 do { 1374 if (Optional<PostStmt> PS = P.getAs<PostStmt>()) { 1375 if (const Expr *Ex = PS->getStmtAs<Expr>()) 1376 reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1377 N->getState().getPtr(), Ex, 1378 N->getLocationContext()); 1379 } 1380 1381 if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) { 1382 const Stmt *S = CE->getCalleeContext()->getCallSite(); 1383 if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) { 1384 reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1385 N->getState().getPtr(), Ex, 1386 N->getLocationContext()); 1387 } 1388 1389 PathDiagnosticCallPiece *C = 1390 PathDiagnosticCallPiece::construct(N, *CE, SM); 1391 LCM[&C->path] = CE->getCalleeContext(); 1392 1393 EB.addEdge(C->callReturn, /*AlwaysAdd=*/true, /*IsPostJump=*/true); 1394 EB.flushLocations(); 1395 1396 PD.getActivePath().push_front(C); 1397 PD.pushActivePath(&C->path); 1398 CallStack.push_back(StackDiagPair(C, N)); 1399 break; 1400 } 1401 1402 // Pop the call hierarchy if we are done walking the contents 1403 // of a function call. 1404 if (Optional<CallEnter> CE = P.getAs<CallEnter>()) { 1405 // Add an edge to the start of the function. 1406 const Decl *D = CE->getCalleeContext()->getDecl(); 1407 PathDiagnosticLocation pos = 1408 PathDiagnosticLocation::createBegin(D, SM); 1409 EB.addEdge(pos); 1410 1411 // Flush all locations, and pop the active path. 1412 bool VisitedEntireCall = PD.isWithinCall(); 1413 EB.flushLocations(); 1414 PD.popActivePath(); 1415 PDB.LC = N->getLocationContext(); 1416 1417 // Either we just added a bunch of stuff to the top-level path, or 1418 // we have a previous CallExitEnd. If the former, it means that the 1419 // path terminated within a function call. We must then take the 1420 // current contents of the active path and place it within 1421 // a new PathDiagnosticCallPiece. 1422 PathDiagnosticCallPiece *C; 1423 if (VisitedEntireCall) { 1424 C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); 1425 } else { 1426 const Decl *Caller = CE->getLocationContext()->getDecl(); 1427 C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 1428 LCM[&C->path] = CE->getCalleeContext(); 1429 } 1430 1431 C->setCallee(*CE, SM); 1432 EB.addContext(C->getLocation()); 1433 1434 if (!CallStack.empty()) { 1435 assert(CallStack.back().first == C); 1436 CallStack.pop_back(); 1437 } 1438 break; 1439 } 1440 1441 // Note that is important that we update the LocationContext 1442 // after looking at CallExits. CallExit basically adds an 1443 // edge in the *caller*, so we don't want to update the LocationContext 1444 // too soon. 1445 PDB.LC = N->getLocationContext(); 1446 1447 // Block edges. 1448 if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) { 1449 // Does this represent entering a call? If so, look at propagating 1450 // interesting symbols across call boundaries. 1451 if (NextNode) { 1452 const LocationContext *CallerCtx = NextNode->getLocationContext(); 1453 const LocationContext *CalleeCtx = PDB.LC; 1454 if (CallerCtx != CalleeCtx) { 1455 reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, 1456 N->getState().getPtr(), 1457 CalleeCtx, CallerCtx); 1458 } 1459 } 1460 1461 // Are we jumping to the head of a loop? Add a special diagnostic. 1462 if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { 1463 PathDiagnosticLocation L(Loop, SM, PDB.LC); 1464 const CompoundStmt *CS = NULL; 1465 1466 if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) 1467 CS = dyn_cast<CompoundStmt>(FS->getBody()); 1468 else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) 1469 CS = dyn_cast<CompoundStmt>(WS->getBody()); 1470 1471 PathDiagnosticEventPiece *p = 1472 new PathDiagnosticEventPiece(L, 1473 "Looping back to the head of the loop"); 1474 p->setPrunable(true); 1475 1476 EB.addEdge(p->getLocation(), true); 1477 PD.getActivePath().push_front(p); 1478 1479 if (CS) { 1480 PathDiagnosticLocation BL = 1481 PathDiagnosticLocation::createEndBrace(CS, SM); 1482 EB.addEdge(BL); 1483 } 1484 } 1485 1486 const CFGBlock *BSrc = BE->getSrc(); 1487 ParentMap &PM = PDB.getParentMap(); 1488 1489 if (const Stmt *Term = BSrc->getTerminator()) { 1490 // Are we jumping past the loop body without ever executing the 1491 // loop (because the condition was false)? 1492 if (isLoopJumpPastBody(Term, &*BE) && 1493 !isInLoopBody(PM, 1494 getStmtBeforeCond(PM, 1495 BSrc->getTerminatorCondition(), 1496 N), 1497 Term)) { 1498 PathDiagnosticLocation L(Term, SM, PDB.LC); 1499 PathDiagnosticEventPiece *PE = 1500 new PathDiagnosticEventPiece(L, "Loop body executed 0 times"); 1501 PE->setPrunable(true); 1502 1503 EB.addEdge(PE->getLocation(), true); 1504 PD.getActivePath().push_front(PE); 1505 } 1506 1507 // In any case, add the terminator as the current statement 1508 // context for control edges. 1509 EB.addContext(Term); 1510 } 1511 1512 break; 1513 } 1514 1515 if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) { 1516 Optional<CFGElement> First = BE->getFirstElement(); 1517 if (Optional<CFGStmt> S = First ? First->getAs<CFGStmt>() : None) { 1518 const Stmt *stmt = S->getStmt(); 1519 if (IsControlFlowExpr(stmt)) { 1520 // Add the proper context for '&&', '||', and '?'. 1521 EB.addContext(stmt); 1522 } 1523 else 1524 EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt()); 1525 } 1526 1527 break; 1528 } 1529 1530 1531 } while (0); 1532 1533 if (!NextNode) 1534 continue; 1535 1536 // Add pieces from custom visitors. 1537 BugReport *R = PDB.getBugReport(); 1538 for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(), 1539 E = visitors.end(); 1540 I != E; ++I) { 1541 if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) { 1542 const PathDiagnosticLocation &Loc = p->getLocation(); 1543 EB.addEdge(Loc, true); 1544 PD.getActivePath().push_front(p); 1545 updateStackPiecesWithMessage(p, CallStack); 1546 1547 if (const Stmt *S = Loc.asStmt()) 1548 EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 1549 } 1550 } 1551 } 1552 1553 return PDB.getBugReport()->isValid(); 1554} 1555 1556/// \brief Adds a sanitized control-flow diagnostic edge to a path. 1557static void addEdgeToPath(PathPieces &path, 1558 PathDiagnosticLocation &PrevLoc, 1559 PathDiagnosticLocation NewLoc, 1560 const LocationContext *LC) { 1561 if (!NewLoc.isValid()) 1562 return; 1563 1564 SourceLocation NewLocL = NewLoc.asLocation(); 1565 if (NewLocL.isInvalid()) 1566 return; 1567 1568 if (!PrevLoc.isValid() || !PrevLoc.asLocation().isValid()) { 1569 PrevLoc = NewLoc; 1570 return; 1571 } 1572 1573 // Ignore self-edges, which occur when there are multiple nodes at the same 1574 // statement. 1575 if (NewLoc.asStmt() && NewLoc.asStmt() == PrevLoc.asStmt()) 1576 return; 1577 1578 path.push_front(new PathDiagnosticControlFlowPiece(NewLoc, 1579 PrevLoc)); 1580 PrevLoc = NewLoc; 1581} 1582 1583/// A customized wrapper for CFGBlock::getTerminatorCondition() 1584/// which returns the element for ObjCForCollectionStmts. 1585static const Stmt *getTerminatorCondition(const CFGBlock *B) { 1586 const Stmt *S = B->getTerminatorCondition(); 1587 if (const ObjCForCollectionStmt *FS = 1588 dyn_cast_or_null<ObjCForCollectionStmt>(S)) 1589 return FS->getElement(); 1590 return S; 1591} 1592 1593static const char *StrEnteringLoop = "Entering loop body"; 1594static const char *StrLoopBodyZero = "Loop body executed 0 times"; 1595 1596static bool 1597GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD, 1598 PathDiagnosticBuilder &PDB, 1599 const ExplodedNode *N, 1600 LocationContextMap &LCM, 1601 ArrayRef<BugReporterVisitor *> visitors) { 1602 1603 BugReport *report = PDB.getBugReport(); 1604 const SourceManager& SM = PDB.getSourceManager(); 1605 StackDiagVector CallStack; 1606 InterestingExprs IE; 1607 1608 PathDiagnosticLocation PrevLoc = PD.getLocation(); 1609 1610 const ExplodedNode *NextNode = N->getFirstPred(); 1611 while (NextNode) { 1612 N = NextNode; 1613 NextNode = N->getFirstPred(); 1614 ProgramPoint P = N->getLocation(); 1615 1616 do { 1617 // Have we encountered an entrance to a call? It may be 1618 // the case that we have not encountered a matching 1619 // call exit before this point. This means that the path 1620 // terminated within the call itself. 1621 if (Optional<CallEnter> CE = P.getAs<CallEnter>()) { 1622 // Add an edge to the start of the function. 1623 const StackFrameContext *CalleeLC = CE->getCalleeContext(); 1624 const Decl *D = CalleeLC->getDecl(); 1625 addEdgeToPath(PD.getActivePath(), PrevLoc, 1626 PathDiagnosticLocation::createBegin(D, SM), 1627 CalleeLC); 1628 1629 // Did we visit an entire call? 1630 bool VisitedEntireCall = PD.isWithinCall(); 1631 PD.popActivePath(); 1632 1633 PathDiagnosticCallPiece *C; 1634 if (VisitedEntireCall) { 1635 PathDiagnosticPiece *P = PD.getActivePath().front().getPtr(); 1636 C = cast<PathDiagnosticCallPiece>(P); 1637 } else { 1638 const Decl *Caller = CE->getLocationContext()->getDecl(); 1639 C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 1640 1641 // Since we just transferred the path over to the call piece, 1642 // reset the mapping from active to location context. 1643 assert(PD.getActivePath().size() == 1 && 1644 PD.getActivePath().front() == C); 1645 LCM[&PD.getActivePath()] = 0; 1646 1647 // Record the location context mapping for the path within 1648 // the call. 1649 assert(LCM[&C->path] == 0 || 1650 LCM[&C->path] == CE->getCalleeContext()); 1651 LCM[&C->path] = CE->getCalleeContext(); 1652 1653 // If this is the first item in the active path, record 1654 // the new mapping from active path to location context. 1655 const LocationContext *&NewLC = LCM[&PD.getActivePath()]; 1656 if (!NewLC) 1657 NewLC = N->getLocationContext(); 1658 1659 PDB.LC = NewLC; 1660 } 1661 C->setCallee(*CE, SM); 1662 1663 // Update the previous location in the active path. 1664 PrevLoc = C->getLocation(); 1665 1666 if (!CallStack.empty()) { 1667 assert(CallStack.back().first == C); 1668 CallStack.pop_back(); 1669 } 1670 break; 1671 } 1672 1673 // Query the location context here and the previous location 1674 // as processing CallEnter may change the active path. 1675 PDB.LC = N->getLocationContext(); 1676 1677 // Record the mapping from the active path to the location 1678 // context. 1679 assert(!LCM[&PD.getActivePath()] || 1680 LCM[&PD.getActivePath()] == PDB.LC); 1681 LCM[&PD.getActivePath()] = PDB.LC; 1682 1683 // Have we encountered an exit from a function call? 1684 if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) { 1685 const Stmt *S = CE->getCalleeContext()->getCallSite(); 1686 // Propagate the interesting symbols accordingly. 1687 if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) { 1688 reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1689 N->getState().getPtr(), Ex, 1690 N->getLocationContext()); 1691 } 1692 1693 // We are descending into a call (backwards). Construct 1694 // a new call piece to contain the path pieces for that call. 1695 PathDiagnosticCallPiece *C = 1696 PathDiagnosticCallPiece::construct(N, *CE, SM); 1697 1698 // Record the location context for this call piece. 1699 LCM[&C->path] = CE->getCalleeContext(); 1700 1701 // Add the edge to the return site. 1702 addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, PDB.LC); 1703 PD.getActivePath().push_front(C); 1704 PrevLoc.invalidate(); 1705 1706 // Make the contents of the call the active path for now. 1707 PD.pushActivePath(&C->path); 1708 CallStack.push_back(StackDiagPair(C, N)); 1709 break; 1710 } 1711 1712 if (Optional<PostStmt> PS = P.getAs<PostStmt>()) { 1713 // For expressions, make sure we propagate the 1714 // interesting symbols correctly. 1715 if (const Expr *Ex = PS->getStmtAs<Expr>()) 1716 reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1717 N->getState().getPtr(), Ex, 1718 N->getLocationContext()); 1719 1720 // Add an edge. If this is an ObjCForCollectionStmt do 1721 // not add an edge here as it appears in the CFG both 1722 // as a terminator and as a terminator condition. 1723 if (!isa<ObjCForCollectionStmt>(PS->getStmt())) { 1724 PathDiagnosticLocation L = 1725 PathDiagnosticLocation(PS->getStmt(), SM, PDB.LC); 1726 addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); 1727 } 1728 break; 1729 } 1730 1731 // Block edges. 1732 if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) { 1733 // Does this represent entering a call? If so, look at propagating 1734 // interesting symbols across call boundaries. 1735 if (NextNode) { 1736 const LocationContext *CallerCtx = NextNode->getLocationContext(); 1737 const LocationContext *CalleeCtx = PDB.LC; 1738 if (CallerCtx != CalleeCtx) { 1739 reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, 1740 N->getState().getPtr(), 1741 CalleeCtx, CallerCtx); 1742 } 1743 } 1744 1745 // Are we jumping to the head of a loop? Add a special diagnostic. 1746 if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { 1747 PathDiagnosticLocation L(Loop, SM, PDB.LC); 1748 const Stmt *Body = NULL; 1749 1750 if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) 1751 Body = FS->getBody(); 1752 else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) 1753 Body = WS->getBody(); 1754 else if (const ObjCForCollectionStmt *OFS = 1755 dyn_cast<ObjCForCollectionStmt>(Loop)) { 1756 Body = OFS->getBody(); 1757 } else if (const CXXForRangeStmt *FRS = 1758 dyn_cast<CXXForRangeStmt>(Loop)) { 1759 Body = FRS->getBody(); 1760 } 1761 // do-while statements are explicitly excluded here 1762 1763 PathDiagnosticEventPiece *p = 1764 new PathDiagnosticEventPiece(L, "Looping back to the head " 1765 "of the loop"); 1766 p->setPrunable(true); 1767 1768 addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC); 1769 PD.getActivePath().push_front(p); 1770 1771 if (const CompoundStmt *CS = dyn_cast_or_null<CompoundStmt>(Body)) { 1772 addEdgeToPath(PD.getActivePath(), PrevLoc, 1773 PathDiagnosticLocation::createEndBrace(CS, SM), 1774 PDB.LC); 1775 } 1776 } 1777 1778 const CFGBlock *BSrc = BE->getSrc(); 1779 ParentMap &PM = PDB.getParentMap(); 1780 1781 if (const Stmt *Term = BSrc->getTerminator()) { 1782 // Are we jumping past the loop body without ever executing the 1783 // loop (because the condition was false)? 1784 if (isLoop(Term)) { 1785 const Stmt *TermCond = getTerminatorCondition(BSrc); 1786 bool IsInLoopBody = 1787 isInLoopBody(PM, getStmtBeforeCond(PM, TermCond, N), Term); 1788 1789 const char *str = 0; 1790 1791 if (isJumpToFalseBranch(&*BE)) { 1792 if (!IsInLoopBody) { 1793 str = StrLoopBodyZero; 1794 } 1795 } 1796 else { 1797 str = StrEnteringLoop; 1798 } 1799 1800 if (str) { 1801 PathDiagnosticLocation L(TermCond ? TermCond : Term, SM, PDB.LC); 1802 PathDiagnosticEventPiece *PE = 1803 new PathDiagnosticEventPiece(L, str); 1804 PE->setPrunable(true); 1805 addEdgeToPath(PD.getActivePath(), PrevLoc, 1806 PE->getLocation(), PDB.LC); 1807 PD.getActivePath().push_front(PE); 1808 } 1809 } 1810 else if (isa<BreakStmt>(Term) || isa<ContinueStmt>(Term) || 1811 isa<GotoStmt>(Term)) { 1812 PathDiagnosticLocation L(Term, SM, PDB.LC); 1813 addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); 1814 } 1815 } 1816 break; 1817 } 1818 } while (0); 1819 1820 if (!NextNode) 1821 continue; 1822 1823 // Add pieces from custom visitors. 1824 for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(), 1825 E = visitors.end(); 1826 I != E; ++I) { 1827 if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *report)) { 1828 addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC); 1829 PD.getActivePath().push_front(p); 1830 updateStackPiecesWithMessage(p, CallStack); 1831 } 1832 } 1833 } 1834 1835 // Add an edge to the start of the function. 1836 // We'll prune it out later, but it helps make diagnostics more uniform. 1837 const StackFrameContext *CalleeLC = PDB.LC->getCurrentStackFrame(); 1838 const Decl *D = CalleeLC->getDecl(); 1839 addEdgeToPath(PD.getActivePath(), PrevLoc, 1840 PathDiagnosticLocation::createBegin(D, SM), 1841 CalleeLC); 1842 1843 return report->isValid(); 1844} 1845 1846static const Stmt *getLocStmt(PathDiagnosticLocation L) { 1847 if (!L.isValid()) 1848 return 0; 1849 return L.asStmt(); 1850} 1851 1852static const Stmt *getStmtParent(const Stmt *S, const ParentMap &PM) { 1853 if (!S) 1854 return 0; 1855 1856 while (true) { 1857 S = PM.getParentIgnoreParens(S); 1858 1859 if (!S) 1860 break; 1861 1862 if (isa<ExprWithCleanups>(S) || 1863 isa<CXXBindTemporaryExpr>(S) || 1864 isa<SubstNonTypeTemplateParmExpr>(S)) 1865 continue; 1866 1867 break; 1868 } 1869 1870 return S; 1871} 1872 1873static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) { 1874 switch (S->getStmtClass()) { 1875 case Stmt::BinaryOperatorClass: { 1876 const BinaryOperator *BO = cast<BinaryOperator>(S); 1877 if (!BO->isLogicalOp()) 1878 return false; 1879 return BO->getLHS() == Cond || BO->getRHS() == Cond; 1880 } 1881 case Stmt::IfStmtClass: 1882 return cast<IfStmt>(S)->getCond() == Cond; 1883 case Stmt::ForStmtClass: 1884 return cast<ForStmt>(S)->getCond() == Cond; 1885 case Stmt::WhileStmtClass: 1886 return cast<WhileStmt>(S)->getCond() == Cond; 1887 case Stmt::DoStmtClass: 1888 return cast<DoStmt>(S)->getCond() == Cond; 1889 case Stmt::ChooseExprClass: 1890 return cast<ChooseExpr>(S)->getCond() == Cond; 1891 case Stmt::IndirectGotoStmtClass: 1892 return cast<IndirectGotoStmt>(S)->getTarget() == Cond; 1893 case Stmt::SwitchStmtClass: 1894 return cast<SwitchStmt>(S)->getCond() == Cond; 1895 case Stmt::BinaryConditionalOperatorClass: 1896 return cast<BinaryConditionalOperator>(S)->getCond() == Cond; 1897 case Stmt::ConditionalOperatorClass: { 1898 const ConditionalOperator *CO = cast<ConditionalOperator>(S); 1899 return CO->getCond() == Cond || 1900 CO->getLHS() == Cond || 1901 CO->getRHS() == Cond; 1902 } 1903 case Stmt::ObjCForCollectionStmtClass: 1904 return cast<ObjCForCollectionStmt>(S)->getElement() == Cond; 1905 case Stmt::CXXForRangeStmtClass: { 1906 const CXXForRangeStmt *FRS = cast<CXXForRangeStmt>(S); 1907 return FRS->getCond() == Cond || FRS->getRangeInit() == Cond; 1908 } 1909 default: 1910 return false; 1911 } 1912} 1913 1914static bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL) { 1915 if (const ForStmt *FS = dyn_cast<ForStmt>(FL)) 1916 return FS->getInc() == S || FS->getInit() == S; 1917 if (const CXXForRangeStmt *FRS = dyn_cast<CXXForRangeStmt>(FL)) 1918 return FRS->getInc() == S || FRS->getRangeStmt() == S || 1919 FRS->getLoopVarStmt() || FRS->getRangeInit() == S; 1920 return false; 1921} 1922 1923typedef llvm::DenseSet<const PathDiagnosticCallPiece *> 1924 OptimizedCallsSet; 1925 1926/// Adds synthetic edges from top-level statements to their subexpressions. 1927/// 1928/// This avoids a "swoosh" effect, where an edge from a top-level statement A 1929/// points to a sub-expression B.1 that's not at the start of B. In these cases, 1930/// we'd like to see an edge from A to B, then another one from B to B.1. 1931static void addContextEdges(PathPieces &pieces, SourceManager &SM, 1932 const ParentMap &PM, const LocationContext *LCtx) { 1933 PathPieces::iterator Prev = pieces.end(); 1934 for (PathPieces::iterator I = pieces.begin(), E = Prev; I != E; 1935 Prev = I, ++I) { 1936 PathDiagnosticControlFlowPiece *Piece = 1937 dyn_cast<PathDiagnosticControlFlowPiece>(*I); 1938 1939 if (!Piece) 1940 continue; 1941 1942 PathDiagnosticLocation SrcLoc = Piece->getStartLocation(); 1943 SmallVector<PathDiagnosticLocation, 4> SrcContexts; 1944 1945 PathDiagnosticLocation NextSrcContext = SrcLoc; 1946 const Stmt *InnerStmt = 0; 1947 while (NextSrcContext.isValid() && NextSrcContext.asStmt() != InnerStmt) { 1948 SrcContexts.push_back(NextSrcContext); 1949 InnerStmt = NextSrcContext.asStmt(); 1950 NextSrcContext = getEnclosingStmtLocation(InnerStmt, SM, PM, LCtx, 1951 /*allowNested=*/true); 1952 } 1953 1954 // Repeatedly split the edge as necessary. 1955 // This is important for nested logical expressions (||, &&, ?:) where we 1956 // want to show all the levels of context. 1957 while (true) { 1958 const Stmt *Dst = getLocStmt(Piece->getEndLocation()); 1959 1960 // We are looking at an edge. Is the destination within a larger 1961 // expression? 1962 PathDiagnosticLocation DstContext = 1963 getEnclosingStmtLocation(Dst, SM, PM, LCtx, /*allowNested=*/true); 1964 if (!DstContext.isValid() || DstContext.asStmt() == Dst) 1965 break; 1966 1967 // If the source is in the same context, we're already good. 1968 if (std::find(SrcContexts.begin(), SrcContexts.end(), DstContext) != 1969 SrcContexts.end()) 1970 break; 1971 1972 // Update the subexpression node to point to the context edge. 1973 Piece->setStartLocation(DstContext); 1974 1975 // Try to extend the previous edge if it's at the same level as the source 1976 // context. 1977 if (Prev != E) { 1978 PathDiagnosticControlFlowPiece *PrevPiece = 1979 dyn_cast<PathDiagnosticControlFlowPiece>(*Prev); 1980 1981 if (PrevPiece) { 1982 if (const Stmt *PrevSrc = getLocStmt(PrevPiece->getStartLocation())) { 1983 const Stmt *PrevSrcParent = getStmtParent(PrevSrc, PM); 1984 if (PrevSrcParent == getStmtParent(getLocStmt(DstContext), PM)) { 1985 PrevPiece->setEndLocation(DstContext); 1986 break; 1987 } 1988 } 1989 } 1990 } 1991 1992 // Otherwise, split the current edge into a context edge and a 1993 // subexpression edge. Note that the context statement may itself have 1994 // context. 1995 Piece = new PathDiagnosticControlFlowPiece(SrcLoc, DstContext); 1996 I = pieces.insert(I, Piece); 1997 } 1998 } 1999} 2000 2001/// \brief Move edges from a branch condition to a branch target 2002/// when the condition is simple. 2003/// 2004/// This restructures some of the work of addContextEdges. That function 2005/// creates edges this may destroy, but they work together to create a more 2006/// aesthetically set of edges around branches. After the call to 2007/// addContextEdges, we may have (1) an edge to the branch, (2) an edge from 2008/// the branch to the branch condition, and (3) an edge from the branch 2009/// condition to the branch target. We keep (1), but may wish to remove (2) 2010/// and move the source of (3) to the branch if the branch condition is simple. 2011/// 2012static void simplifySimpleBranches(PathPieces &pieces) { 2013 for (PathPieces::iterator I = pieces.begin(), E = pieces.end(); I != E; ++I) { 2014 2015 PathDiagnosticControlFlowPiece *PieceI = 2016 dyn_cast<PathDiagnosticControlFlowPiece>(*I); 2017 2018 if (!PieceI) 2019 continue; 2020 2021 const Stmt *s1Start = getLocStmt(PieceI->getStartLocation()); 2022 const Stmt *s1End = getLocStmt(PieceI->getEndLocation()); 2023 2024 if (!s1Start || !s1End) 2025 continue; 2026 2027 PathPieces::iterator NextI = I; ++NextI; 2028 if (NextI == E) 2029 break; 2030 2031 PathDiagnosticControlFlowPiece *PieceNextI = 0; 2032 2033 while (true) { 2034 if (NextI == E) 2035 break; 2036 2037 PathDiagnosticEventPiece *EV = dyn_cast<PathDiagnosticEventPiece>(*NextI); 2038 if (EV) { 2039 StringRef S = EV->getString(); 2040 if (S == StrEnteringLoop || S == StrLoopBodyZero) { 2041 ++NextI; 2042 continue; 2043 } 2044 break; 2045 } 2046 2047 PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); 2048 break; 2049 } 2050 2051 if (!PieceNextI) 2052 continue; 2053 2054 const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation()); 2055 const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation()); 2056 2057 if (!s2Start || !s2End || s1End != s2Start) 2058 continue; 2059 2060 // We only perform this transformation for specific branch kinds. 2061 // We don't want to do this for do..while, for example. 2062 if (!(isa<ForStmt>(s1Start) || isa<WhileStmt>(s1Start) || 2063 isa<IfStmt>(s1Start) || isa<ObjCForCollectionStmt>(s1Start) || 2064 isa<CXXForRangeStmt>(s1Start))) 2065 continue; 2066 2067 // Is s1End the branch condition? 2068 if (!isConditionForTerminator(s1Start, s1End)) 2069 continue; 2070 2071 // Perform the hoisting by eliminating (2) and changing the start 2072 // location of (3). 2073 PieceNextI->setStartLocation(PieceI->getStartLocation()); 2074 I = pieces.erase(I); 2075 } 2076} 2077 2078/// Returns the number of bytes in the given (character-based) SourceRange. 2079/// 2080/// If the locations in the range are not on the same line, returns None. 2081/// 2082/// Note that this does not do a precise user-visible character or column count. 2083static Optional<size_t> getLengthOnSingleLine(SourceManager &SM, 2084 SourceRange Range) { 2085 SourceRange ExpansionRange(SM.getExpansionLoc(Range.getBegin()), 2086 SM.getExpansionRange(Range.getEnd()).second); 2087 2088 FileID FID = SM.getFileID(ExpansionRange.getBegin()); 2089 if (FID != SM.getFileID(ExpansionRange.getEnd())) 2090 return None; 2091 2092 bool Invalid; 2093 const llvm::MemoryBuffer *Buffer = SM.getBuffer(FID, &Invalid); 2094 if (Invalid) 2095 return None; 2096 2097 unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin()); 2098 unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd()); 2099 StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset); 2100 2101 // We're searching the raw bytes of the buffer here, which might include 2102 // escaped newlines and such. That's okay; we're trying to decide whether the 2103 // SourceRange is covering a large or small amount of space in the user's 2104 // editor. 2105 if (Snippet.find_first_of("\r\n") != StringRef::npos) 2106 return None; 2107 2108 // This isn't Unicode-aware, but it doesn't need to be. 2109 return Snippet.size(); 2110} 2111 2112/// \sa getLengthOnSingleLine(SourceManager, SourceRange) 2113static Optional<size_t> getLengthOnSingleLine(SourceManager &SM, 2114 const Stmt *S) { 2115 return getLengthOnSingleLine(SM, S->getSourceRange()); 2116} 2117 2118/// Eliminate two-edge cycles created by addContextEdges(). 2119/// 2120/// Once all the context edges are in place, there are plenty of cases where 2121/// there's a single edge from a top-level statement to a subexpression, 2122/// followed by a single path note, and then a reverse edge to get back out to 2123/// the top level. If the statement is simple enough, the subexpression edges 2124/// just add noise and make it harder to understand what's going on. 2125/// 2126/// This function only removes edges in pairs, because removing only one edge 2127/// might leave other edges dangling. 2128/// 2129/// This will not remove edges in more complicated situations: 2130/// - if there is more than one "hop" leading to or from a subexpression. 2131/// - if there is an inlined call between the edges instead of a single event. 2132/// - if the whole statement is large enough that having subexpression arrows 2133/// might be helpful. 2134static void removeContextCycles(PathPieces &Path, SourceManager &SM, 2135 ParentMap &PM) { 2136 for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) { 2137 // Pattern match the current piece and its successor. 2138 PathDiagnosticControlFlowPiece *PieceI = 2139 dyn_cast<PathDiagnosticControlFlowPiece>(*I); 2140 2141 if (!PieceI) { 2142 ++I; 2143 continue; 2144 } 2145 2146 const Stmt *s1Start = getLocStmt(PieceI->getStartLocation()); 2147 const Stmt *s1End = getLocStmt(PieceI->getEndLocation()); 2148 2149 PathPieces::iterator NextI = I; ++NextI; 2150 if (NextI == E) 2151 break; 2152 2153 PathDiagnosticControlFlowPiece *PieceNextI = 2154 dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); 2155 2156 if (!PieceNextI) { 2157 if (isa<PathDiagnosticEventPiece>(*NextI)) { 2158 ++NextI; 2159 if (NextI == E) 2160 break; 2161 PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); 2162 } 2163 2164 if (!PieceNextI) { 2165 ++I; 2166 continue; 2167 } 2168 } 2169 2170 const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation()); 2171 const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation()); 2172 2173 if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) { 2174 const size_t MAX_SHORT_LINE_LENGTH = 80; 2175 Optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start); 2176 if (s1Length && *s1Length <= MAX_SHORT_LINE_LENGTH) { 2177 Optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start); 2178 if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) { 2179 Path.erase(I); 2180 I = Path.erase(NextI); 2181 continue; 2182 } 2183 } 2184 } 2185 2186 ++I; 2187 } 2188} 2189 2190/// \brief Return true if X is contained by Y. 2191static bool lexicalContains(ParentMap &PM, 2192 const Stmt *X, 2193 const Stmt *Y) { 2194 while (X) { 2195 if (X == Y) 2196 return true; 2197 X = PM.getParent(X); 2198 } 2199 return false; 2200} 2201 2202// Remove short edges on the same line less than 3 columns in difference. 2203static void removePunyEdges(PathPieces &path, 2204 SourceManager &SM, 2205 ParentMap &PM) { 2206 2207 bool erased = false; 2208 2209 for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; 2210 erased ? I : ++I) { 2211 2212 erased = false; 2213 2214 PathDiagnosticControlFlowPiece *PieceI = 2215 dyn_cast<PathDiagnosticControlFlowPiece>(*I); 2216 2217 if (!PieceI) 2218 continue; 2219 2220 const Stmt *start = getLocStmt(PieceI->getStartLocation()); 2221 const Stmt *end = getLocStmt(PieceI->getEndLocation()); 2222 2223 if (!start || !end) 2224 continue; 2225 2226 const Stmt *endParent = PM.getParent(end); 2227 if (!endParent) 2228 continue; 2229 2230 if (isConditionForTerminator(end, endParent)) 2231 continue; 2232 2233 SourceLocation FirstLoc = start->getLocStart(); 2234 SourceLocation SecondLoc = end->getLocStart(); 2235 2236 if (!SM.isFromSameFile(FirstLoc, SecondLoc)) 2237 continue; 2238 if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc)) 2239 std::swap(SecondLoc, FirstLoc); 2240 2241 SourceRange EdgeRange(FirstLoc, SecondLoc); 2242 Optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange); 2243 2244 // If the statements are on different lines, continue. 2245 if (!ByteWidth) 2246 continue; 2247 2248 const size_t MAX_PUNY_EDGE_LENGTH = 2; 2249 if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) { 2250 // FIXME: There are enough /bytes/ between the endpoints of the edge, but 2251 // there might not be enough /columns/. A proper user-visible column count 2252 // is probably too expensive, though. 2253 I = path.erase(I); 2254 erased = true; 2255 continue; 2256 } 2257 } 2258} 2259 2260static void removeIdenticalEvents(PathPieces &path) { 2261 for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) { 2262 PathDiagnosticEventPiece *PieceI = 2263 dyn_cast<PathDiagnosticEventPiece>(*I); 2264 2265 if (!PieceI) 2266 continue; 2267 2268 PathPieces::iterator NextI = I; ++NextI; 2269 if (NextI == E) 2270 return; 2271 2272 PathDiagnosticEventPiece *PieceNextI = 2273 dyn_cast<PathDiagnosticEventPiece>(*NextI); 2274 2275 if (!PieceNextI) 2276 continue; 2277 2278 // Erase the second piece if it has the same exact message text. 2279 if (PieceI->getString() == PieceNextI->getString()) { 2280 path.erase(NextI); 2281 } 2282 } 2283} 2284 2285static bool optimizeEdges(PathPieces &path, SourceManager &SM, 2286 OptimizedCallsSet &OCS, 2287 LocationContextMap &LCM) { 2288 bool hasChanges = false; 2289 const LocationContext *LC = LCM[&path]; 2290 assert(LC); 2291 ParentMap &PM = LC->getParentMap(); 2292 2293 for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) { 2294 // Optimize subpaths. 2295 if (PathDiagnosticCallPiece *CallI = dyn_cast<PathDiagnosticCallPiece>(*I)){ 2296 // Record the fact that a call has been optimized so we only do the 2297 // effort once. 2298 if (!OCS.count(CallI)) { 2299 while (optimizeEdges(CallI->path, SM, OCS, LCM)) {} 2300 OCS.insert(CallI); 2301 } 2302 ++I; 2303 continue; 2304 } 2305 2306 // Pattern match the current piece and its successor. 2307 PathDiagnosticControlFlowPiece *PieceI = 2308 dyn_cast<PathDiagnosticControlFlowPiece>(*I); 2309 2310 if (!PieceI) { 2311 ++I; 2312 continue; 2313 } 2314 2315 const Stmt *s1Start = getLocStmt(PieceI->getStartLocation()); 2316 const Stmt *s1End = getLocStmt(PieceI->getEndLocation()); 2317 const Stmt *level1 = getStmtParent(s1Start, PM); 2318 const Stmt *level2 = getStmtParent(s1End, PM); 2319 2320 PathPieces::iterator NextI = I; ++NextI; 2321 if (NextI == E) 2322 break; 2323 2324 PathDiagnosticControlFlowPiece *PieceNextI = 2325 dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); 2326 2327 if (!PieceNextI) { 2328 ++I; 2329 continue; 2330 } 2331 2332 const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation()); 2333 const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation()); 2334 const Stmt *level3 = getStmtParent(s2Start, PM); 2335 const Stmt *level4 = getStmtParent(s2End, PM); 2336 2337 // Rule I. 2338 // 2339 // If we have two consecutive control edges whose end/begin locations 2340 // are at the same level (e.g. statements or top-level expressions within 2341 // a compound statement, or siblings share a single ancestor expression), 2342 // then merge them if they have no interesting intermediate event. 2343 // 2344 // For example: 2345 // 2346 // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common 2347 // parent is '1'. Here 'x.y.z' represents the hierarchy of statements. 2348 // 2349 // NOTE: this will be limited later in cases where we add barriers 2350 // to prevent this optimization. 2351 // 2352 if (level1 && level1 == level2 && level1 == level3 && level1 == level4) { 2353 PieceI->setEndLocation(PieceNextI->getEndLocation()); 2354 path.erase(NextI); 2355 hasChanges = true; 2356 continue; 2357 } 2358 2359 // Rule II. 2360 // 2361 // Eliminate edges between subexpressions and parent expressions 2362 // when the subexpression is consumed. 2363 // 2364 // NOTE: this will be limited later in cases where we add barriers 2365 // to prevent this optimization. 2366 // 2367 if (s1End && s1End == s2Start && level2) { 2368 bool removeEdge = false; 2369 // Remove edges into the increment or initialization of a 2370 // loop that have no interleaving event. This means that 2371 // they aren't interesting. 2372 if (isIncrementOrInitInForLoop(s1End, level2)) 2373 removeEdge = true; 2374 // Next only consider edges that are not anchored on 2375 // the condition of a terminator. This are intermediate edges 2376 // that we might want to trim. 2377 else if (!isConditionForTerminator(level2, s1End)) { 2378 // Trim edges on expressions that are consumed by 2379 // the parent expression. 2380 if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) { 2381 removeEdge = true; 2382 } 2383 // Trim edges where a lexical containment doesn't exist. 2384 // For example: 2385 // 2386 // X -> Y -> Z 2387 // 2388 // If 'Z' lexically contains Y (it is an ancestor) and 2389 // 'X' does not lexically contain Y (it is a descendant OR 2390 // it has no lexical relationship at all) then trim. 2391 // 2392 // This can eliminate edges where we dive into a subexpression 2393 // and then pop back out, etc. 2394 else if (s1Start && s2End && 2395 lexicalContains(PM, s2Start, s2End) && 2396 !lexicalContains(PM, s1End, s1Start)) { 2397 removeEdge = true; 2398 } 2399 // Trim edges from a subexpression back to the top level if the 2400 // subexpression is on a different line. 2401 // 2402 // A.1 -> A -> B 2403 // becomes 2404 // A.1 -> B 2405 // 2406 // These edges just look ugly and don't usually add anything. 2407 else if (s1Start && s2End && 2408 lexicalContains(PM, s1Start, s1End)) { 2409 SourceRange EdgeRange(PieceI->getEndLocation().asLocation(), 2410 PieceI->getStartLocation().asLocation()); 2411 if (!getLengthOnSingleLine(SM, EdgeRange).hasValue()) 2412 removeEdge = true; 2413 } 2414 } 2415 2416 if (removeEdge) { 2417 PieceI->setEndLocation(PieceNextI->getEndLocation()); 2418 path.erase(NextI); 2419 hasChanges = true; 2420 continue; 2421 } 2422 } 2423 2424 // Optimize edges for ObjC fast-enumeration loops. 2425 // 2426 // (X -> collection) -> (collection -> element) 2427 // 2428 // becomes: 2429 // 2430 // (X -> element) 2431 if (s1End == s2Start) { 2432 const ObjCForCollectionStmt *FS = 2433 dyn_cast_or_null<ObjCForCollectionStmt>(level3); 2434 if (FS && FS->getCollection()->IgnoreParens() == s2Start && 2435 s2End == FS->getElement()) { 2436 PieceI->setEndLocation(PieceNextI->getEndLocation()); 2437 path.erase(NextI); 2438 hasChanges = true; 2439 continue; 2440 } 2441 } 2442 2443 // No changes at this index? Move to the next one. 2444 ++I; 2445 } 2446 2447 if (!hasChanges) { 2448 // Adjust edges into subexpressions to make them more uniform 2449 // and aesthetically pleasing. 2450 addContextEdges(path, SM, PM, LC); 2451 // Remove "cyclical" edges that include one or more context edges. 2452 removeContextCycles(path, SM, PM); 2453 // Hoist edges originating from branch conditions to branches 2454 // for simple branches. 2455 simplifySimpleBranches(path); 2456 // Remove any puny edges left over after primary optimization pass. 2457 removePunyEdges(path, SM, PM); 2458 // Remove identical events. 2459 removeIdenticalEvents(path); 2460 } 2461 2462 return hasChanges; 2463} 2464 2465/// Drop the very first edge in a path, which should be a function entry edge. 2466/// 2467/// If the first edge is not a function entry edge (say, because the first 2468/// statement had an invalid source location), this function does nothing. 2469// FIXME: We should just generate invalid edges anyway and have the optimizer 2470// deal with them. 2471static void dropFunctionEntryEdge(PathPieces &Path, 2472 LocationContextMap &LCM, 2473 SourceManager &SM) { 2474 const PathDiagnosticControlFlowPiece *FirstEdge = 2475 dyn_cast<PathDiagnosticControlFlowPiece>(Path.front()); 2476 if (!FirstEdge) 2477 return; 2478 2479 const Decl *D = LCM[&Path]->getDecl(); 2480 PathDiagnosticLocation EntryLoc = PathDiagnosticLocation::createBegin(D, SM); 2481 if (FirstEdge->getStartLocation() != EntryLoc) 2482 return; 2483 2484 Path.pop_front(); 2485} 2486 2487 2488//===----------------------------------------------------------------------===// 2489// Methods for BugType and subclasses. 2490//===----------------------------------------------------------------------===// 2491BugType::~BugType() { } 2492 2493void BugType::FlushReports(BugReporter &BR) {} 2494 2495void BuiltinBug::anchor() {} 2496 2497//===----------------------------------------------------------------------===// 2498// Methods for BugReport and subclasses. 2499//===----------------------------------------------------------------------===// 2500 2501void BugReport::NodeResolver::anchor() {} 2502 2503void BugReport::addVisitor(BugReporterVisitor* visitor) { 2504 if (!visitor) 2505 return; 2506 2507 llvm::FoldingSetNodeID ID; 2508 visitor->Profile(ID); 2509 void *InsertPos; 2510 2511 if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) { 2512 delete visitor; 2513 return; 2514 } 2515 2516 CallbacksSet.InsertNode(visitor, InsertPos); 2517 Callbacks.push_back(visitor); 2518 ++ConfigurationChangeToken; 2519} 2520 2521BugReport::~BugReport() { 2522 for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I) { 2523 delete *I; 2524 } 2525 while (!interestingSymbols.empty()) { 2526 popInterestingSymbolsAndRegions(); 2527 } 2528} 2529 2530const Decl *BugReport::getDeclWithIssue() const { 2531 if (DeclWithIssue) 2532 return DeclWithIssue; 2533 2534 const ExplodedNode *N = getErrorNode(); 2535 if (!N) 2536 return 0; 2537 2538 const LocationContext *LC = N->getLocationContext(); 2539 return LC->getCurrentStackFrame()->getDecl(); 2540} 2541 2542void BugReport::Profile(llvm::FoldingSetNodeID& hash) const { 2543 hash.AddPointer(&BT); 2544 hash.AddString(Description); 2545 PathDiagnosticLocation UL = getUniqueingLocation(); 2546 if (UL.isValid()) { 2547 UL.Profile(hash); 2548 } else if (Location.isValid()) { 2549 Location.Profile(hash); 2550 } else { 2551 assert(ErrorNode); 2552 hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode)); 2553 } 2554 2555 for (SmallVectorImpl<SourceRange>::const_iterator I = 2556 Ranges.begin(), E = Ranges.end(); I != E; ++I) { 2557 const SourceRange range = *I; 2558 if (!range.isValid()) 2559 continue; 2560 hash.AddInteger(range.getBegin().getRawEncoding()); 2561 hash.AddInteger(range.getEnd().getRawEncoding()); 2562 } 2563} 2564 2565void BugReport::markInteresting(SymbolRef sym) { 2566 if (!sym) 2567 return; 2568 2569 // If the symbol wasn't already in our set, note a configuration change. 2570 if (getInterestingSymbols().insert(sym).second) 2571 ++ConfigurationChangeToken; 2572 2573 if (const SymbolMetadata *meta = dyn_cast<SymbolMetadata>(sym)) 2574 getInterestingRegions().insert(meta->getRegion()); 2575} 2576 2577void BugReport::markInteresting(const MemRegion *R) { 2578 if (!R) 2579 return; 2580 2581 // If the base region wasn't already in our set, note a configuration change. 2582 R = R->getBaseRegion(); 2583 if (getInterestingRegions().insert(R).second) 2584 ++ConfigurationChangeToken; 2585 2586 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 2587 getInterestingSymbols().insert(SR->getSymbol()); 2588} 2589 2590void BugReport::markInteresting(SVal V) { 2591 markInteresting(V.getAsRegion()); 2592 markInteresting(V.getAsSymbol()); 2593} 2594 2595void BugReport::markInteresting(const LocationContext *LC) { 2596 if (!LC) 2597 return; 2598 InterestingLocationContexts.insert(LC); 2599} 2600 2601bool BugReport::isInteresting(SVal V) { 2602 return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol()); 2603} 2604 2605bool BugReport::isInteresting(SymbolRef sym) { 2606 if (!sym) 2607 return false; 2608 // We don't currently consider metadata symbols to be interesting 2609 // even if we know their region is interesting. Is that correct behavior? 2610 return getInterestingSymbols().count(sym); 2611} 2612 2613bool BugReport::isInteresting(const MemRegion *R) { 2614 if (!R) 2615 return false; 2616 R = R->getBaseRegion(); 2617 bool b = getInterestingRegions().count(R); 2618 if (b) 2619 return true; 2620 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 2621 return getInterestingSymbols().count(SR->getSymbol()); 2622 return false; 2623} 2624 2625bool BugReport::isInteresting(const LocationContext *LC) { 2626 if (!LC) 2627 return false; 2628 return InterestingLocationContexts.count(LC); 2629} 2630 2631void BugReport::lazyInitializeInterestingSets() { 2632 if (interestingSymbols.empty()) { 2633 interestingSymbols.push_back(new Symbols()); 2634 interestingRegions.push_back(new Regions()); 2635 } 2636} 2637 2638BugReport::Symbols &BugReport::getInterestingSymbols() { 2639 lazyInitializeInterestingSets(); 2640 return *interestingSymbols.back(); 2641} 2642 2643BugReport::Regions &BugReport::getInterestingRegions() { 2644 lazyInitializeInterestingSets(); 2645 return *interestingRegions.back(); 2646} 2647 2648void BugReport::pushInterestingSymbolsAndRegions() { 2649 interestingSymbols.push_back(new Symbols(getInterestingSymbols())); 2650 interestingRegions.push_back(new Regions(getInterestingRegions())); 2651} 2652 2653void BugReport::popInterestingSymbolsAndRegions() { 2654 delete interestingSymbols.back(); 2655 interestingSymbols.pop_back(); 2656 delete interestingRegions.back(); 2657 interestingRegions.pop_back(); 2658} 2659 2660const Stmt *BugReport::getStmt() const { 2661 if (!ErrorNode) 2662 return 0; 2663 2664 ProgramPoint ProgP = ErrorNode->getLocation(); 2665 const Stmt *S = NULL; 2666 2667 if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) { 2668 CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit(); 2669 if (BE->getBlock() == &Exit) 2670 S = GetPreviousStmt(ErrorNode); 2671 } 2672 if (!S) 2673 S = PathDiagnosticLocation::getStmt(ErrorNode); 2674 2675 return S; 2676} 2677 2678std::pair<BugReport::ranges_iterator, BugReport::ranges_iterator> 2679BugReport::getRanges() { 2680 // If no custom ranges, add the range of the statement corresponding to 2681 // the error node. 2682 if (Ranges.empty()) { 2683 if (const Expr *E = dyn_cast_or_null<Expr>(getStmt())) 2684 addRange(E->getSourceRange()); 2685 else 2686 return std::make_pair(ranges_iterator(), ranges_iterator()); 2687 } 2688 2689 // User-specified absence of range info. 2690 if (Ranges.size() == 1 && !Ranges.begin()->isValid()) 2691 return std::make_pair(ranges_iterator(), ranges_iterator()); 2692 2693 return std::make_pair(Ranges.begin(), Ranges.end()); 2694} 2695 2696PathDiagnosticLocation BugReport::getLocation(const SourceManager &SM) const { 2697 if (ErrorNode) { 2698 assert(!Location.isValid() && 2699 "Either Location or ErrorNode should be specified but not both."); 2700 return PathDiagnosticLocation::createEndOfPath(ErrorNode, SM); 2701 } else { 2702 assert(Location.isValid()); 2703 return Location; 2704 } 2705 2706 return PathDiagnosticLocation(); 2707} 2708 2709//===----------------------------------------------------------------------===// 2710// Methods for BugReporter and subclasses. 2711//===----------------------------------------------------------------------===// 2712 2713BugReportEquivClass::~BugReportEquivClass() { } 2714GRBugReporter::~GRBugReporter() { } 2715BugReporterData::~BugReporterData() {} 2716 2717ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); } 2718 2719ProgramStateManager& 2720GRBugReporter::getStateManager() { return Eng.getStateManager(); } 2721 2722BugReporter::~BugReporter() { 2723 FlushReports(); 2724 2725 // Free the bug reports we are tracking. 2726 typedef std::vector<BugReportEquivClass *> ContTy; 2727 for (ContTy::iterator I = EQClassesVector.begin(), E = EQClassesVector.end(); 2728 I != E; ++I) { 2729 delete *I; 2730 } 2731} 2732 2733void BugReporter::FlushReports() { 2734 if (BugTypes.isEmpty()) 2735 return; 2736 2737 // First flush the warnings for each BugType. This may end up creating new 2738 // warnings and new BugTypes. 2739 // FIXME: Only NSErrorChecker needs BugType's FlushReports. 2740 // Turn NSErrorChecker into a proper checker and remove this. 2741 SmallVector<const BugType*, 16> bugTypes; 2742 for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I) 2743 bugTypes.push_back(*I); 2744 for (SmallVector<const BugType*, 16>::iterator 2745 I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I) 2746 const_cast<BugType*>(*I)->FlushReports(*this); 2747 2748 // We need to flush reports in deterministic order to ensure the order 2749 // of the reports is consistent between runs. 2750 typedef std::vector<BugReportEquivClass *> ContVecTy; 2751 for (ContVecTy::iterator EI=EQClassesVector.begin(), EE=EQClassesVector.end(); 2752 EI != EE; ++EI){ 2753 BugReportEquivClass& EQ = **EI; 2754 FlushReport(EQ); 2755 } 2756 2757 // BugReporter owns and deletes only BugTypes created implicitly through 2758 // EmitBasicReport. 2759 // FIXME: There are leaks from checkers that assume that the BugTypes they 2760 // create will be destroyed by the BugReporter. 2761 for (llvm::StringMap<BugType*>::iterator 2762 I = StrBugTypes.begin(), E = StrBugTypes.end(); I != E; ++I) 2763 delete I->second; 2764 2765 // Remove all references to the BugType objects. 2766 BugTypes = F.getEmptySet(); 2767} 2768 2769//===----------------------------------------------------------------------===// 2770// PathDiagnostics generation. 2771//===----------------------------------------------------------------------===// 2772 2773namespace { 2774/// A wrapper around a report graph, which contains only a single path, and its 2775/// node maps. 2776class ReportGraph { 2777public: 2778 InterExplodedGraphMap BackMap; 2779 OwningPtr<ExplodedGraph> Graph; 2780 const ExplodedNode *ErrorNode; 2781 size_t Index; 2782}; 2783 2784/// A wrapper around a trimmed graph and its node maps. 2785class TrimmedGraph { 2786 InterExplodedGraphMap InverseMap; 2787 2788 typedef llvm::DenseMap<const ExplodedNode *, unsigned> PriorityMapTy; 2789 PriorityMapTy PriorityMap; 2790 2791 typedef std::pair<const ExplodedNode *, size_t> NodeIndexPair; 2792 SmallVector<NodeIndexPair, 32> ReportNodes; 2793 2794 OwningPtr<ExplodedGraph> G; 2795 2796 /// A helper class for sorting ExplodedNodes by priority. 2797 template <bool Descending> 2798 class PriorityCompare { 2799 const PriorityMapTy &PriorityMap; 2800 2801 public: 2802 PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {} 2803 2804 bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const { 2805 PriorityMapTy::const_iterator LI = PriorityMap.find(LHS); 2806 PriorityMapTy::const_iterator RI = PriorityMap.find(RHS); 2807 PriorityMapTy::const_iterator E = PriorityMap.end(); 2808 2809 if (LI == E) 2810 return Descending; 2811 if (RI == E) 2812 return !Descending; 2813 2814 return Descending ? LI->second > RI->second 2815 : LI->second < RI->second; 2816 } 2817 2818 bool operator()(const NodeIndexPair &LHS, const NodeIndexPair &RHS) const { 2819 return (*this)(LHS.first, RHS.first); 2820 } 2821 }; 2822 2823public: 2824 TrimmedGraph(const ExplodedGraph *OriginalGraph, 2825 ArrayRef<const ExplodedNode *> Nodes); 2826 2827 bool popNextReportGraph(ReportGraph &GraphWrapper); 2828}; 2829} 2830 2831TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph, 2832 ArrayRef<const ExplodedNode *> Nodes) { 2833 // The trimmed graph is created in the body of the constructor to ensure 2834 // that the DenseMaps have been initialized already. 2835 InterExplodedGraphMap ForwardMap; 2836 G.reset(OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap)); 2837 2838 // Find the (first) error node in the trimmed graph. We just need to consult 2839 // the node map which maps from nodes in the original graph to nodes 2840 // in the new graph. 2841 llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes; 2842 2843 for (unsigned i = 0, count = Nodes.size(); i < count; ++i) { 2844 if (const ExplodedNode *NewNode = ForwardMap.lookup(Nodes[i])) { 2845 ReportNodes.push_back(std::make_pair(NewNode, i)); 2846 RemainingNodes.insert(NewNode); 2847 } 2848 } 2849 2850 assert(!RemainingNodes.empty() && "No error node found in the trimmed graph"); 2851 2852 // Perform a forward BFS to find all the shortest paths. 2853 std::queue<const ExplodedNode *> WS; 2854 2855 assert(G->num_roots() == 1); 2856 WS.push(*G->roots_begin()); 2857 unsigned Priority = 0; 2858 2859 while (!WS.empty()) { 2860 const ExplodedNode *Node = WS.front(); 2861 WS.pop(); 2862 2863 PriorityMapTy::iterator PriorityEntry; 2864 bool IsNew; 2865 llvm::tie(PriorityEntry, IsNew) = 2866 PriorityMap.insert(std::make_pair(Node, Priority)); 2867 ++Priority; 2868 2869 if (!IsNew) { 2870 assert(PriorityEntry->second <= Priority); 2871 continue; 2872 } 2873 2874 if (RemainingNodes.erase(Node)) 2875 if (RemainingNodes.empty()) 2876 break; 2877 2878 for (ExplodedNode::const_pred_iterator I = Node->succ_begin(), 2879 E = Node->succ_end(); 2880 I != E; ++I) 2881 WS.push(*I); 2882 } 2883 2884 // Sort the error paths from longest to shortest. 2885 std::sort(ReportNodes.begin(), ReportNodes.end(), 2886 PriorityCompare<true>(PriorityMap)); 2887} 2888 2889bool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) { 2890 if (ReportNodes.empty()) 2891 return false; 2892 2893 const ExplodedNode *OrigN; 2894 llvm::tie(OrigN, GraphWrapper.Index) = ReportNodes.pop_back_val(); 2895 assert(PriorityMap.find(OrigN) != PriorityMap.end() && 2896 "error node not accessible from root"); 2897 2898 // Create a new graph with a single path. This is the graph 2899 // that will be returned to the caller. 2900 ExplodedGraph *GNew = new ExplodedGraph(); 2901 GraphWrapper.Graph.reset(GNew); 2902 GraphWrapper.BackMap.clear(); 2903 2904 // Now walk from the error node up the BFS path, always taking the 2905 // predeccessor with the lowest number. 2906 ExplodedNode *Succ = 0; 2907 while (true) { 2908 // Create the equivalent node in the new graph with the same state 2909 // and location. 2910 ExplodedNode *NewN = GNew->getNode(OrigN->getLocation(), OrigN->getState(), 2911 OrigN->isSink()); 2912 2913 // Store the mapping to the original node. 2914 InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN); 2915 assert(IMitr != InverseMap.end() && "No mapping to original node."); 2916 GraphWrapper.BackMap[NewN] = IMitr->second; 2917 2918 // Link up the new node with the previous node. 2919 if (Succ) 2920 Succ->addPredecessor(NewN, *GNew); 2921 else 2922 GraphWrapper.ErrorNode = NewN; 2923 2924 Succ = NewN; 2925 2926 // Are we at the final node? 2927 if (OrigN->pred_empty()) { 2928 GNew->addRoot(NewN); 2929 break; 2930 } 2931 2932 // Find the next predeccessor node. We choose the node that is marked 2933 // with the lowest BFS number. 2934 OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(), 2935 PriorityCompare<false>(PriorityMap)); 2936 } 2937 2938 return true; 2939} 2940 2941 2942/// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object 2943/// and collapses PathDiagosticPieces that are expanded by macros. 2944static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) { 2945 typedef std::vector<std::pair<IntrusiveRefCntPtr<PathDiagnosticMacroPiece>, 2946 SourceLocation> > MacroStackTy; 2947 2948 typedef std::vector<IntrusiveRefCntPtr<PathDiagnosticPiece> > 2949 PiecesTy; 2950 2951 MacroStackTy MacroStack; 2952 PiecesTy Pieces; 2953 2954 for (PathPieces::const_iterator I = path.begin(), E = path.end(); 2955 I!=E; ++I) { 2956 2957 PathDiagnosticPiece *piece = I->getPtr(); 2958 2959 // Recursively compact calls. 2960 if (PathDiagnosticCallPiece *call=dyn_cast<PathDiagnosticCallPiece>(piece)){ 2961 CompactPathDiagnostic(call->path, SM); 2962 } 2963 2964 // Get the location of the PathDiagnosticPiece. 2965 const FullSourceLoc Loc = piece->getLocation().asLocation(); 2966 2967 // Determine the instantiation location, which is the location we group 2968 // related PathDiagnosticPieces. 2969 SourceLocation InstantiationLoc = Loc.isMacroID() ? 2970 SM.getExpansionLoc(Loc) : 2971 SourceLocation(); 2972 2973 if (Loc.isFileID()) { 2974 MacroStack.clear(); 2975 Pieces.push_back(piece); 2976 continue; 2977 } 2978 2979 assert(Loc.isMacroID()); 2980 2981 // Is the PathDiagnosticPiece within the same macro group? 2982 if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) { 2983 MacroStack.back().first->subPieces.push_back(piece); 2984 continue; 2985 } 2986 2987 // We aren't in the same group. Are we descending into a new macro 2988 // or are part of an old one? 2989 IntrusiveRefCntPtr<PathDiagnosticMacroPiece> MacroGroup; 2990 2991 SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ? 2992 SM.getExpansionLoc(Loc) : 2993 SourceLocation(); 2994 2995 // Walk the entire macro stack. 2996 while (!MacroStack.empty()) { 2997 if (InstantiationLoc == MacroStack.back().second) { 2998 MacroGroup = MacroStack.back().first; 2999 break; 3000 } 3001 3002 if (ParentInstantiationLoc == MacroStack.back().second) { 3003 MacroGroup = MacroStack.back().first; 3004 break; 3005 } 3006 3007 MacroStack.pop_back(); 3008 } 3009 3010 if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) { 3011 // Create a new macro group and add it to the stack. 3012 PathDiagnosticMacroPiece *NewGroup = 3013 new PathDiagnosticMacroPiece( 3014 PathDiagnosticLocation::createSingleLocation(piece->getLocation())); 3015 3016 if (MacroGroup) 3017 MacroGroup->subPieces.push_back(NewGroup); 3018 else { 3019 assert(InstantiationLoc.isFileID()); 3020 Pieces.push_back(NewGroup); 3021 } 3022 3023 MacroGroup = NewGroup; 3024 MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc)); 3025 } 3026 3027 // Finally, add the PathDiagnosticPiece to the group. 3028 MacroGroup->subPieces.push_back(piece); 3029 } 3030 3031 // Now take the pieces and construct a new PathDiagnostic. 3032 path.clear(); 3033 3034 for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I) 3035 path.push_back(*I); 3036} 3037 3038bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD, 3039 PathDiagnosticConsumer &PC, 3040 ArrayRef<BugReport *> &bugReports) { 3041 assert(!bugReports.empty()); 3042 3043 bool HasValid = false; 3044 bool HasInvalid = false; 3045 SmallVector<const ExplodedNode *, 32> errorNodes; 3046 for (ArrayRef<BugReport*>::iterator I = bugReports.begin(), 3047 E = bugReports.end(); I != E; ++I) { 3048 if ((*I)->isValid()) { 3049 HasValid = true; 3050 errorNodes.push_back((*I)->getErrorNode()); 3051 } else { 3052 // Keep the errorNodes list in sync with the bugReports list. 3053 HasInvalid = true; 3054 errorNodes.push_back(0); 3055 } 3056 } 3057 3058 // If all the reports have been marked invalid by a previous path generation, 3059 // we're done. 3060 if (!HasValid) 3061 return false; 3062 3063 typedef PathDiagnosticConsumer::PathGenerationScheme PathGenerationScheme; 3064 PathGenerationScheme ActiveScheme = PC.getGenerationScheme(); 3065 3066 if (ActiveScheme == PathDiagnosticConsumer::Extensive) { 3067 AnalyzerOptions &options = getAnalyzerOptions(); 3068 if (options.getBooleanOption("path-diagnostics-alternate", true)) { 3069 ActiveScheme = PathDiagnosticConsumer::AlternateExtensive; 3070 } 3071 } 3072 3073 TrimmedGraph TrimG(&getGraph(), errorNodes); 3074 ReportGraph ErrorGraph; 3075 3076 while (TrimG.popNextReportGraph(ErrorGraph)) { 3077 // Find the BugReport with the original location. 3078 assert(ErrorGraph.Index < bugReports.size()); 3079 BugReport *R = bugReports[ErrorGraph.Index]; 3080 assert(R && "No original report found for sliced graph."); 3081 assert(R->isValid() && "Report selected by trimmed graph marked invalid."); 3082 3083 // Start building the path diagnostic... 3084 PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, &PC); 3085 const ExplodedNode *N = ErrorGraph.ErrorNode; 3086 3087 // Register additional node visitors. 3088 R->addVisitor(new NilReceiverBRVisitor()); 3089 R->addVisitor(new ConditionBRVisitor()); 3090 R->addVisitor(new LikelyFalsePositiveSuppressionBRVisitor()); 3091 3092 BugReport::VisitorList visitors; 3093 unsigned origReportConfigToken, finalReportConfigToken; 3094 LocationContextMap LCM; 3095 3096 // While generating diagnostics, it's possible the visitors will decide 3097 // new symbols and regions are interesting, or add other visitors based on 3098 // the information they find. If they do, we need to regenerate the path 3099 // based on our new report configuration. 3100 do { 3101 // Get a clean copy of all the visitors. 3102 for (BugReport::visitor_iterator I = R->visitor_begin(), 3103 E = R->visitor_end(); I != E; ++I) 3104 visitors.push_back((*I)->clone()); 3105 3106 // Clear out the active path from any previous work. 3107 PD.resetPath(); 3108 origReportConfigToken = R->getConfigurationChangeToken(); 3109 3110 // Generate the very last diagnostic piece - the piece is visible before 3111 // the trace is expanded. 3112 PathDiagnosticPiece *LastPiece = 0; 3113 for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end(); 3114 I != E; ++I) { 3115 if (PathDiagnosticPiece *Piece = (*I)->getEndPath(PDB, N, *R)) { 3116 assert (!LastPiece && 3117 "There can only be one final piece in a diagnostic."); 3118 LastPiece = Piece; 3119 } 3120 } 3121 3122 if (ActiveScheme != PathDiagnosticConsumer::None) { 3123 if (!LastPiece) 3124 LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R); 3125 assert(LastPiece); 3126 PD.setEndOfPath(LastPiece); 3127 } 3128 3129 // Make sure we get a clean location context map so we don't 3130 // hold onto old mappings. 3131 LCM.clear(); 3132 3133 switch (ActiveScheme) { 3134 case PathDiagnosticConsumer::AlternateExtensive: 3135 GenerateAlternateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors); 3136 break; 3137 case PathDiagnosticConsumer::Extensive: 3138 GenerateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors); 3139 break; 3140 case PathDiagnosticConsumer::Minimal: 3141 GenerateMinimalPathDiagnostic(PD, PDB, N, LCM, visitors); 3142 break; 3143 case PathDiagnosticConsumer::None: 3144 GenerateVisitorsOnlyPathDiagnostic(PD, PDB, N, visitors); 3145 break; 3146 } 3147 3148 // Clean up the visitors we used. 3149 llvm::DeleteContainerPointers(visitors); 3150 3151 // Did anything change while generating this path? 3152 finalReportConfigToken = R->getConfigurationChangeToken(); 3153 } while (finalReportConfigToken != origReportConfigToken); 3154 3155 if (!R->isValid()) 3156 continue; 3157 3158 // Finally, prune the diagnostic path of uninteresting stuff. 3159 if (!PD.path.empty()) { 3160 if (R->shouldPrunePath() && getAnalyzerOptions().shouldPrunePaths()) { 3161 bool stillHasNotes = removeUnneededCalls(PD.getMutablePieces(), R, LCM); 3162 assert(stillHasNotes); 3163 (void)stillHasNotes; 3164 } 3165 3166 // Redirect all call pieces to have valid locations. 3167 adjustCallLocations(PD.getMutablePieces()); 3168 3169 removePiecesWithInvalidLocations(PD.getMutablePieces()); 3170 3171 if (ActiveScheme == PathDiagnosticConsumer::AlternateExtensive) { 3172 SourceManager &SM = getSourceManager(); 3173 3174 // Reduce the number of edges from a very conservative set 3175 // to an aesthetically pleasing subset that conveys the 3176 // necessary information. 3177 OptimizedCallsSet OCS; 3178 while (optimizeEdges(PD.getMutablePieces(), SM, OCS, LCM)) {} 3179 3180 // Drop the very first function-entry edge. It's not really necessary 3181 // for top-level functions. 3182 dropFunctionEntryEdge(PD.getMutablePieces(), LCM, SM); 3183 } 3184 3185 // Remove messages that are basically the same. 3186 // We have to do this after edge optimization in the Extensive mode. 3187 removeRedundantMsgs(PD.getMutablePieces()); 3188 } 3189 3190 // We found a report and didn't suppress it. 3191 return true; 3192 } 3193 3194 // We suppressed all the reports in this equivalence class. 3195 assert(!HasInvalid && "Inconsistent suppression"); 3196 (void)HasInvalid; 3197 return false; 3198} 3199 3200void BugReporter::Register(BugType *BT) { 3201 BugTypes = F.add(BugTypes, BT); 3202} 3203 3204void BugReporter::emitReport(BugReport* R) { 3205 // Compute the bug report's hash to determine its equivalence class. 3206 llvm::FoldingSetNodeID ID; 3207 R->Profile(ID); 3208 3209 // Lookup the equivance class. If there isn't one, create it. 3210 BugType& BT = R->getBugType(); 3211 Register(&BT); 3212 void *InsertPos; 3213 BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos); 3214 3215 if (!EQ) { 3216 EQ = new BugReportEquivClass(R); 3217 EQClasses.InsertNode(EQ, InsertPos); 3218 EQClassesVector.push_back(EQ); 3219 } 3220 else 3221 EQ->AddReport(R); 3222} 3223 3224 3225//===----------------------------------------------------------------------===// 3226// Emitting reports in equivalence classes. 3227//===----------------------------------------------------------------------===// 3228 3229namespace { 3230struct FRIEC_WLItem { 3231 const ExplodedNode *N; 3232 ExplodedNode::const_succ_iterator I, E; 3233 3234 FRIEC_WLItem(const ExplodedNode *n) 3235 : N(n), I(N->succ_begin()), E(N->succ_end()) {} 3236}; 3237} 3238 3239static BugReport * 3240FindReportInEquivalenceClass(BugReportEquivClass& EQ, 3241 SmallVectorImpl<BugReport*> &bugReports) { 3242 3243 BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end(); 3244 assert(I != E); 3245 BugType& BT = I->getBugType(); 3246 3247 // If we don't need to suppress any of the nodes because they are 3248 // post-dominated by a sink, simply add all the nodes in the equivalence class 3249 // to 'Nodes'. Any of the reports will serve as a "representative" report. 3250 if (!BT.isSuppressOnSink()) { 3251 BugReport *R = I; 3252 for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) { 3253 const ExplodedNode *N = I->getErrorNode(); 3254 if (N) { 3255 R = I; 3256 bugReports.push_back(R); 3257 } 3258 } 3259 return R; 3260 } 3261 3262 // For bug reports that should be suppressed when all paths are post-dominated 3263 // by a sink node, iterate through the reports in the equivalence class 3264 // until we find one that isn't post-dominated (if one exists). We use a 3265 // DFS traversal of the ExplodedGraph to find a non-sink node. We could write 3266 // this as a recursive function, but we don't want to risk blowing out the 3267 // stack for very long paths. 3268 BugReport *exampleReport = 0; 3269 3270 for (; I != E; ++I) { 3271 const ExplodedNode *errorNode = I->getErrorNode(); 3272 3273 if (!errorNode) 3274 continue; 3275 if (errorNode->isSink()) { 3276 llvm_unreachable( 3277 "BugType::isSuppressSink() should not be 'true' for sink end nodes"); 3278 } 3279 // No successors? By definition this nodes isn't post-dominated by a sink. 3280 if (errorNode->succ_empty()) { 3281 bugReports.push_back(I); 3282 if (!exampleReport) 3283 exampleReport = I; 3284 continue; 3285 } 3286 3287 // At this point we know that 'N' is not a sink and it has at least one 3288 // successor. Use a DFS worklist to find a non-sink end-of-path node. 3289 typedef FRIEC_WLItem WLItem; 3290 typedef SmallVector<WLItem, 10> DFSWorkList; 3291 llvm::DenseMap<const ExplodedNode *, unsigned> Visited; 3292 3293 DFSWorkList WL; 3294 WL.push_back(errorNode); 3295 Visited[errorNode] = 1; 3296 3297 while (!WL.empty()) { 3298 WLItem &WI = WL.back(); 3299 assert(!WI.N->succ_empty()); 3300 3301 for (; WI.I != WI.E; ++WI.I) { 3302 const ExplodedNode *Succ = *WI.I; 3303 // End-of-path node? 3304 if (Succ->succ_empty()) { 3305 // If we found an end-of-path node that is not a sink. 3306 if (!Succ->isSink()) { 3307 bugReports.push_back(I); 3308 if (!exampleReport) 3309 exampleReport = I; 3310 WL.clear(); 3311 break; 3312 } 3313 // Found a sink? Continue on to the next successor. 3314 continue; 3315 } 3316 // Mark the successor as visited. If it hasn't been explored, 3317 // enqueue it to the DFS worklist. 3318 unsigned &mark = Visited[Succ]; 3319 if (!mark) { 3320 mark = 1; 3321 WL.push_back(Succ); 3322 break; 3323 } 3324 } 3325 3326 // The worklist may have been cleared at this point. First 3327 // check if it is empty before checking the last item. 3328 if (!WL.empty() && &WL.back() == &WI) 3329 WL.pop_back(); 3330 } 3331 } 3332 3333 // ExampleReport will be NULL if all the nodes in the equivalence class 3334 // were post-dominated by sinks. 3335 return exampleReport; 3336} 3337 3338void BugReporter::FlushReport(BugReportEquivClass& EQ) { 3339 SmallVector<BugReport*, 10> bugReports; 3340 BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports); 3341 if (exampleReport) { 3342 const PathDiagnosticConsumers &C = getPathDiagnosticConsumers(); 3343 for (PathDiagnosticConsumers::const_iterator I=C.begin(), 3344 E=C.end(); I != E; ++I) { 3345 FlushReport(exampleReport, **I, bugReports); 3346 } 3347 } 3348} 3349 3350void BugReporter::FlushReport(BugReport *exampleReport, 3351 PathDiagnosticConsumer &PD, 3352 ArrayRef<BugReport*> bugReports) { 3353 3354 // FIXME: Make sure we use the 'R' for the path that was actually used. 3355 // Probably doesn't make a difference in practice. 3356 BugType& BT = exampleReport->getBugType(); 3357 3358 OwningPtr<PathDiagnostic> 3359 D(new PathDiagnostic(exampleReport->getDeclWithIssue(), 3360 exampleReport->getBugType().getName(), 3361 exampleReport->getDescription(), 3362 exampleReport->getShortDescription(/*Fallback=*/false), 3363 BT.getCategory(), 3364 exampleReport->getUniqueingLocation(), 3365 exampleReport->getUniqueingDecl())); 3366 3367 MaxBugClassSize = std::max(bugReports.size(), 3368 static_cast<size_t>(MaxBugClassSize)); 3369 3370 // Generate the full path diagnostic, using the generation scheme 3371 // specified by the PathDiagnosticConsumer. Note that we have to generate 3372 // path diagnostics even for consumers which do not support paths, because 3373 // the BugReporterVisitors may mark this bug as a false positive. 3374 if (!bugReports.empty()) 3375 if (!generatePathDiagnostic(*D.get(), PD, bugReports)) 3376 return; 3377 3378 MaxValidBugClassSize = std::max(bugReports.size(), 3379 static_cast<size_t>(MaxValidBugClassSize)); 3380 3381 // Examine the report and see if the last piece is in a header. Reset the 3382 // report location to the last piece in the main source file. 3383 AnalyzerOptions& Opts = getAnalyzerOptions(); 3384 if (Opts.shouldReportIssuesInMainSourceFile() && !Opts.AnalyzeAll) 3385 D->resetDiagnosticLocationToMainFile(); 3386 3387 // If the path is empty, generate a single step path with the location 3388 // of the issue. 3389 if (D->path.empty()) { 3390 PathDiagnosticLocation L = exampleReport->getLocation(getSourceManager()); 3391 PathDiagnosticPiece *piece = 3392 new PathDiagnosticEventPiece(L, exampleReport->getDescription()); 3393 BugReport::ranges_iterator Beg, End; 3394 llvm::tie(Beg, End) = exampleReport->getRanges(); 3395 for ( ; Beg != End; ++Beg) 3396 piece->addRange(*Beg); 3397 D->setEndOfPath(piece); 3398 } 3399 3400 // Get the meta data. 3401 const BugReport::ExtraTextList &Meta = exampleReport->getExtraText(); 3402 for (BugReport::ExtraTextList::const_iterator i = Meta.begin(), 3403 e = Meta.end(); i != e; ++i) { 3404 D->addMeta(*i); 3405 } 3406 3407 PD.HandlePathDiagnostic(D.take()); 3408} 3409 3410void BugReporter::EmitBasicReport(const Decl *DeclWithIssue, 3411 StringRef name, 3412 StringRef category, 3413 StringRef str, PathDiagnosticLocation Loc, 3414 SourceRange* RBeg, unsigned NumRanges) { 3415 3416 // 'BT' is owned by BugReporter. 3417 BugType *BT = getBugTypeForName(name, category); 3418 BugReport *R = new BugReport(*BT, str, Loc); 3419 R->setDeclWithIssue(DeclWithIssue); 3420 for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg); 3421 emitReport(R); 3422} 3423 3424BugType *BugReporter::getBugTypeForName(StringRef name, 3425 StringRef category) { 3426 SmallString<136> fullDesc; 3427 llvm::raw_svector_ostream(fullDesc) << name << ":" << category; 3428 llvm::StringMapEntry<BugType *> & 3429 entry = StrBugTypes.GetOrCreateValue(fullDesc); 3430 BugType *BT = entry.getValue(); 3431 if (!BT) { 3432 BT = new BugType(name, category); 3433 entry.setValue(BT); 3434 } 3435 return BT; 3436} 3437 3438 3439void PathPieces::dump() const { 3440 unsigned index = 0; 3441 for (PathPieces::const_iterator I = begin(), E = end(); I != E; ++I) { 3442 llvm::errs() << "[" << index++ << "] "; 3443 (*I)->dump(); 3444 llvm::errs() << "\n"; 3445 } 3446} 3447 3448void PathDiagnosticCallPiece::dump() const { 3449 llvm::errs() << "CALL\n--------------\n"; 3450 3451 if (const Stmt *SLoc = getLocStmt(getLocation())) 3452 SLoc->dump(); 3453 else if (const NamedDecl *ND = dyn_cast<NamedDecl>(getCallee())) 3454 llvm::errs() << *ND << "\n"; 3455 else 3456 getLocation().dump(); 3457} 3458 3459void PathDiagnosticEventPiece::dump() const { 3460 llvm::errs() << "EVENT\n--------------\n"; 3461 llvm::errs() << getString() << "\n"; 3462 llvm::errs() << " ---- at ----\n"; 3463 getLocation().dump(); 3464} 3465 3466void PathDiagnosticControlFlowPiece::dump() const { 3467 llvm::errs() << "CONTROL\n--------------\n"; 3468 getStartLocation().dump(); 3469 llvm::errs() << " ---- to ----\n"; 3470 getEndLocation().dump(); 3471} 3472 3473void PathDiagnosticMacroPiece::dump() const { 3474 llvm::errs() << "MACRO\n--------------\n"; 3475 // FIXME: Print which macro is being invoked. 3476} 3477 3478void PathDiagnosticLocation::dump() const { 3479 if (!isValid()) { 3480 llvm::errs() << "<INVALID>\n"; 3481 return; 3482 } 3483 3484 switch (K) { 3485 case RangeK: 3486 // FIXME: actually print the range. 3487 llvm::errs() << "<range>\n"; 3488 break; 3489 case SingleLocK: 3490 asLocation().dump(); 3491 llvm::errs() << "\n"; 3492 break; 3493 case StmtK: 3494 if (S) 3495 S->dump(); 3496 else 3497 llvm::errs() << "<NULL STMT>\n"; 3498 break; 3499 case DeclK: 3500 if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D)) 3501 llvm::errs() << *ND << "\n"; 3502 else if (isa<BlockDecl>(D)) 3503 // FIXME: Make this nicer. 3504 llvm::errs() << "<block>\n"; 3505 else if (D) 3506 llvm::errs() << "<unknown decl>\n"; 3507 else 3508 llvm::errs() << "<NULL DECL>\n"; 3509 break; 3510 } 3511} 3512