BugReporter.cpp revision 280031
1218887Sdim// BugReporter.cpp - Generate PathDiagnostics for Bugs ------------*- C++ -*--// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines BugReporter, a utility class for generating 11218887Sdim// PathDiagnostics. 12218887Sdim// 13218887Sdim//===----------------------------------------------------------------------===// 14218887Sdim 15218887Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 16218887Sdim#include "clang/AST/ASTContext.h" 17234353Sdim#include "clang/AST/DeclObjC.h" 18218887Sdim#include "clang/AST/Expr.h" 19261991Sdim#include "clang/AST/ExprCXX.h" 20218887Sdim#include "clang/AST/ParentMap.h" 21276479Sdim#include "clang/AST/StmtCXX.h" 22218887Sdim#include "clang/AST/StmtObjC.h" 23249423Sdim#include "clang/Analysis/CFG.h" 24249423Sdim#include "clang/Analysis/ProgramPoint.h" 25218887Sdim#include "clang/Basic/SourceManager.h" 26249423Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 27218887Sdim#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" 28249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 29218887Sdim#include "llvm/ADT/DenseMap.h" 30249423Sdim#include "llvm/ADT/IntrusiveRefCntPtr.h" 31249423Sdim#include "llvm/ADT/STLExtras.h" 32234353Sdim#include "llvm/ADT/SmallString.h" 33249423Sdim#include "llvm/ADT/Statistic.h" 34249423Sdim#include "llvm/Support/raw_ostream.h" 35276479Sdim#include <memory> 36218887Sdim#include <queue> 37218887Sdim 38218887Sdimusing namespace clang; 39218887Sdimusing namespace ento; 40218887Sdim 41276479Sdim#define DEBUG_TYPE "BugReporter" 42276479Sdim 43249423SdimSTATISTIC(MaxBugClassSize, 44249423Sdim "The maximum number of bug reports in the same equivalence class"); 45249423SdimSTATISTIC(MaxValidBugClassSize, 46249423Sdim "The maximum number of bug reports in the same equivalence class " 47249423Sdim "where at least one report is valid (not suppressed)"); 48249423Sdim 49218887SdimBugReporterVisitor::~BugReporterVisitor() {} 50218887Sdim 51234353Sdimvoid BugReporterContext::anchor() {} 52234353Sdim 53218887Sdim//===----------------------------------------------------------------------===// 54218887Sdim// Helper routines for walking the ExplodedGraph and fetching statements. 55218887Sdim//===----------------------------------------------------------------------===// 56218887Sdim 57226633Sdimstatic const Stmt *GetPreviousStmt(const ExplodedNode *N) { 58251662Sdim for (N = N->getFirstPred(); N; N = N->getFirstPred()) 59251662Sdim if (const Stmt *S = PathDiagnosticLocation::getStmt(N)) 60218887Sdim return S; 61218887Sdim 62276479Sdim return nullptr; 63218887Sdim} 64218887Sdim 65218887Sdimstatic inline const Stmt* 66226633SdimGetCurrentOrPreviousStmt(const ExplodedNode *N) { 67251662Sdim if (const Stmt *S = PathDiagnosticLocation::getStmt(N)) 68218887Sdim return S; 69218887Sdim 70218887Sdim return GetPreviousStmt(N); 71218887Sdim} 72218887Sdim 73218887Sdim//===----------------------------------------------------------------------===// 74234353Sdim// Diagnostic cleanup. 75234353Sdim//===----------------------------------------------------------------------===// 76234353Sdim 77243830Sdimstatic PathDiagnosticEventPiece * 78243830SdimeventsDescribeSameCondition(PathDiagnosticEventPiece *X, 79243830Sdim PathDiagnosticEventPiece *Y) { 80243830Sdim // Prefer diagnostics that come from ConditionBRVisitor over 81243830Sdim // those that came from TrackConstraintBRVisitor. 82243830Sdim const void *tagPreferred = ConditionBRVisitor::getTag(); 83243830Sdim const void *tagLesser = TrackConstraintBRVisitor::getTag(); 84243830Sdim 85243830Sdim if (X->getLocation() != Y->getLocation()) 86276479Sdim return nullptr; 87276479Sdim 88243830Sdim if (X->getTag() == tagPreferred && Y->getTag() == tagLesser) 89243830Sdim return X; 90243830Sdim 91243830Sdim if (Y->getTag() == tagPreferred && X->getTag() == tagLesser) 92243830Sdim return Y; 93276479Sdim 94276479Sdim return nullptr; 95243830Sdim} 96243830Sdim 97243830Sdim/// An optimization pass over PathPieces that removes redundant diagnostics 98243830Sdim/// generated by both ConditionBRVisitor and TrackConstraintBRVisitor. Both 99243830Sdim/// BugReporterVisitors use different methods to generate diagnostics, with 100243830Sdim/// one capable of emitting diagnostics in some cases but not in others. This 101243830Sdim/// can lead to redundant diagnostic pieces at the same point in a path. 102243830Sdimstatic void removeRedundantMsgs(PathPieces &path) { 103243830Sdim unsigned N = path.size(); 104243830Sdim if (N < 2) 105243830Sdim return; 106243830Sdim // NOTE: this loop intentionally is not using an iterator. Instead, we 107243830Sdim // are streaming the path and modifying it in place. This is done by 108243830Sdim // grabbing the front, processing it, and if we decide to keep it append 109243830Sdim // it to the end of the path. The entire path is processed in this way. 110243830Sdim for (unsigned i = 0; i < N; ++i) { 111243830Sdim IntrusiveRefCntPtr<PathDiagnosticPiece> piece(path.front()); 112243830Sdim path.pop_front(); 113243830Sdim 114243830Sdim switch (piece->getKind()) { 115243830Sdim case clang::ento::PathDiagnosticPiece::Call: 116243830Sdim removeRedundantMsgs(cast<PathDiagnosticCallPiece>(piece)->path); 117243830Sdim break; 118243830Sdim case clang::ento::PathDiagnosticPiece::Macro: 119243830Sdim removeRedundantMsgs(cast<PathDiagnosticMacroPiece>(piece)->subPieces); 120243830Sdim break; 121243830Sdim case clang::ento::PathDiagnosticPiece::ControlFlow: 122243830Sdim break; 123243830Sdim case clang::ento::PathDiagnosticPiece::Event: { 124243830Sdim if (i == N-1) 125243830Sdim break; 126243830Sdim 127243830Sdim if (PathDiagnosticEventPiece *nextEvent = 128276479Sdim dyn_cast<PathDiagnosticEventPiece>(path.front().get())) { 129243830Sdim PathDiagnosticEventPiece *event = 130243830Sdim cast<PathDiagnosticEventPiece>(piece); 131243830Sdim // Check to see if we should keep one of the two pieces. If we 132243830Sdim // come up with a preference, record which piece to keep, and consume 133243830Sdim // another piece from the path. 134243830Sdim if (PathDiagnosticEventPiece *pieceToKeep = 135243830Sdim eventsDescribeSameCondition(event, nextEvent)) { 136243830Sdim piece = pieceToKeep; 137243830Sdim path.pop_front(); 138243830Sdim ++i; 139243830Sdim } 140243830Sdim } 141243830Sdim break; 142243830Sdim } 143243830Sdim } 144243830Sdim path.push_back(piece); 145243830Sdim } 146243830Sdim} 147243830Sdim 148251662Sdim/// A map from PathDiagnosticPiece to the LocationContext of the inlined 149251662Sdim/// function call it represents. 150251662Sdimtypedef llvm::DenseMap<const PathPieces *, const LocationContext *> 151251662Sdim LocationContextMap; 152251662Sdim 153234353Sdim/// Recursively scan through a path and prune out calls and macros pieces 154234353Sdim/// that aren't needed. Return true if afterwards the path contains 155249423Sdim/// "interesting stuff" which means it shouldn't be pruned from the parent path. 156251662Sdimstatic bool removeUnneededCalls(PathPieces &pieces, BugReport *R, 157251662Sdim LocationContextMap &LCM) { 158234353Sdim bool containsSomethingInteresting = false; 159234353Sdim const unsigned N = pieces.size(); 160234353Sdim 161234353Sdim for (unsigned i = 0 ; i < N ; ++i) { 162234353Sdim // Remove the front piece from the path. If it is still something we 163234353Sdim // want to keep once we are done, we will push it back on the end. 164234353Sdim IntrusiveRefCntPtr<PathDiagnosticPiece> piece(pieces.front()); 165234353Sdim pieces.pop_front(); 166234353Sdim 167234353Sdim switch (piece->getKind()) { 168234353Sdim case PathDiagnosticPiece::Call: { 169234353Sdim PathDiagnosticCallPiece *call = cast<PathDiagnosticCallPiece>(piece); 170243830Sdim // Check if the location context is interesting. 171251662Sdim assert(LCM.count(&call->path)); 172251662Sdim if (R->isInteresting(LCM[&call->path])) { 173243830Sdim containsSomethingInteresting = true; 174243830Sdim break; 175243830Sdim } 176249423Sdim 177251662Sdim if (!removeUnneededCalls(call->path, R, LCM)) 178234353Sdim continue; 179243830Sdim 180234353Sdim containsSomethingInteresting = true; 181234353Sdim break; 182234353Sdim } 183234353Sdim case PathDiagnosticPiece::Macro: { 184234353Sdim PathDiagnosticMacroPiece *macro = cast<PathDiagnosticMacroPiece>(piece); 185251662Sdim if (!removeUnneededCalls(macro->subPieces, R, LCM)) 186234353Sdim continue; 187234353Sdim containsSomethingInteresting = true; 188234353Sdim break; 189234353Sdim } 190234353Sdim case PathDiagnosticPiece::Event: { 191234353Sdim PathDiagnosticEventPiece *event = cast<PathDiagnosticEventPiece>(piece); 192243830Sdim 193234353Sdim // We never throw away an event, but we do throw it away wholesale 194234353Sdim // as part of a path if we throw the entire path away. 195243830Sdim containsSomethingInteresting |= !event->isPrunable(); 196234353Sdim break; 197234353Sdim } 198234353Sdim case PathDiagnosticPiece::ControlFlow: 199234353Sdim break; 200234353Sdim } 201234353Sdim 202234353Sdim pieces.push_back(piece); 203234353Sdim } 204234353Sdim 205234353Sdim return containsSomethingInteresting; 206234353Sdim} 207234353Sdim 208261991Sdim/// Returns true if the given decl has been implicitly given a body, either by 209261991Sdim/// the analyzer or by the compiler proper. 210261991Sdimstatic bool hasImplicitBody(const Decl *D) { 211261991Sdim assert(D); 212261991Sdim return D->isImplicit() || !D->hasBody(); 213261991Sdim} 214261991Sdim 215249423Sdim/// Recursively scan through a path and make sure that all call pieces have 216261991Sdim/// valid locations. 217276479Sdimstatic void 218276479SdimadjustCallLocations(PathPieces &Pieces, 219276479Sdim PathDiagnosticLocation *LastCallLocation = nullptr) { 220249423Sdim for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E; ++I) { 221249423Sdim PathDiagnosticCallPiece *Call = dyn_cast<PathDiagnosticCallPiece>(*I); 222249423Sdim 223249423Sdim if (!Call) { 224249423Sdim assert((*I)->getLocation().asLocation().isValid()); 225249423Sdim continue; 226249423Sdim } 227249423Sdim 228249423Sdim if (LastCallLocation) { 229261991Sdim bool CallerIsImplicit = hasImplicitBody(Call->getCaller()); 230261991Sdim if (CallerIsImplicit || !Call->callEnter.asLocation().isValid()) 231249423Sdim Call->callEnter = *LastCallLocation; 232261991Sdim if (CallerIsImplicit || !Call->callReturn.asLocation().isValid()) 233249423Sdim Call->callReturn = *LastCallLocation; 234249423Sdim } 235249423Sdim 236249423Sdim // Recursively clean out the subclass. Keep this call around if 237249423Sdim // it contains any informative diagnostics. 238249423Sdim PathDiagnosticLocation *ThisCallLocation; 239249423Sdim if (Call->callEnterWithin.asLocation().isValid() && 240261991Sdim !hasImplicitBody(Call->getCallee())) 241249423Sdim ThisCallLocation = &Call->callEnterWithin; 242249423Sdim else 243249423Sdim ThisCallLocation = &Call->callEnter; 244249423Sdim 245249423Sdim assert(ThisCallLocation && "Outermost call has an invalid location"); 246249423Sdim adjustCallLocations(Call->path, ThisCallLocation); 247249423Sdim } 248249423Sdim} 249249423Sdim 250261991Sdim/// Remove edges in and out of C++ default initializer expressions. These are 251261991Sdim/// for fields that have in-class initializers, as opposed to being initialized 252261991Sdim/// explicitly in a constructor or braced list. 253261991Sdimstatic void removeEdgesToDefaultInitializers(PathPieces &Pieces) { 254261991Sdim for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) { 255261991Sdim if (PathDiagnosticCallPiece *C = dyn_cast<PathDiagnosticCallPiece>(*I)) 256261991Sdim removeEdgesToDefaultInitializers(C->path); 257261991Sdim 258261991Sdim if (PathDiagnosticMacroPiece *M = dyn_cast<PathDiagnosticMacroPiece>(*I)) 259261991Sdim removeEdgesToDefaultInitializers(M->subPieces); 260261991Sdim 261261991Sdim if (PathDiagnosticControlFlowPiece *CF = 262261991Sdim dyn_cast<PathDiagnosticControlFlowPiece>(*I)) { 263261991Sdim const Stmt *Start = CF->getStartLocation().asStmt(); 264261991Sdim const Stmt *End = CF->getEndLocation().asStmt(); 265261991Sdim if (Start && isa<CXXDefaultInitExpr>(Start)) { 266261991Sdim I = Pieces.erase(I); 267261991Sdim continue; 268261991Sdim } else if (End && isa<CXXDefaultInitExpr>(End)) { 269276479Sdim PathPieces::iterator Next = std::next(I); 270261991Sdim if (Next != E) { 271261991Sdim if (PathDiagnosticControlFlowPiece *NextCF = 272261991Sdim dyn_cast<PathDiagnosticControlFlowPiece>(*Next)) { 273261991Sdim NextCF->setStartLocation(CF->getStartLocation()); 274261991Sdim } 275261991Sdim } 276261991Sdim I = Pieces.erase(I); 277261991Sdim continue; 278261991Sdim } 279261991Sdim } 280261991Sdim 281261991Sdim I++; 282261991Sdim } 283261991Sdim} 284261991Sdim 285261991Sdim/// Remove all pieces with invalid locations as these cannot be serialized. 286261991Sdim/// We might have pieces with invalid locations as a result of inlining Body 287261991Sdim/// Farm generated functions. 288261991Sdimstatic void removePiecesWithInvalidLocations(PathPieces &Pieces) { 289261991Sdim for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) { 290261991Sdim if (PathDiagnosticCallPiece *C = dyn_cast<PathDiagnosticCallPiece>(*I)) 291261991Sdim removePiecesWithInvalidLocations(C->path); 292261991Sdim 293261991Sdim if (PathDiagnosticMacroPiece *M = dyn_cast<PathDiagnosticMacroPiece>(*I)) 294261991Sdim removePiecesWithInvalidLocations(M->subPieces); 295261991Sdim 296261991Sdim if (!(*I)->getLocation().isValid() || 297261991Sdim !(*I)->getLocation().asLocation().isValid()) { 298261991Sdim I = Pieces.erase(I); 299261991Sdim continue; 300261991Sdim } 301261991Sdim I++; 302261991Sdim } 303261991Sdim} 304261991Sdim 305234353Sdim//===----------------------------------------------------------------------===// 306218887Sdim// PathDiagnosticBuilder and its associated routines and helper objects. 307218887Sdim//===----------------------------------------------------------------------===// 308218887Sdim 309218887Sdimnamespace { 310218887Sdimclass NodeMapClosure : public BugReport::NodeResolver { 311249423Sdim InterExplodedGraphMap &M; 312218887Sdimpublic: 313249423Sdim NodeMapClosure(InterExplodedGraphMap &m) : M(m) {} 314218887Sdim 315276479Sdim const ExplodedNode *getOriginalNode(const ExplodedNode *N) override { 316249423Sdim return M.lookup(N); 317218887Sdim } 318218887Sdim}; 319218887Sdim 320218887Sdimclass PathDiagnosticBuilder : public BugReporterContext { 321218887Sdim BugReport *R; 322226633Sdim PathDiagnosticConsumer *PDC; 323218887Sdim NodeMapClosure NMC; 324218887Sdimpublic: 325234353Sdim const LocationContext *LC; 326234353Sdim 327218887Sdim PathDiagnosticBuilder(GRBugReporter &br, 328249423Sdim BugReport *r, InterExplodedGraphMap &Backmap, 329226633Sdim PathDiagnosticConsumer *pdc) 330218887Sdim : BugReporterContext(br), 331234353Sdim R(r), PDC(pdc), NMC(Backmap), LC(r->getErrorNode()->getLocationContext()) 332234353Sdim {} 333218887Sdim 334226633Sdim PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N); 335218887Sdim 336226633Sdim PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os, 337226633Sdim const ExplodedNode *N); 338218887Sdim 339226633Sdim BugReport *getBugReport() { return R; } 340226633Sdim 341218887Sdim Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); } 342234353Sdim 343234353Sdim ParentMap& getParentMap() { return LC->getParentMap(); } 344218887Sdim 345218887Sdim const Stmt *getParent(const Stmt *S) { 346218887Sdim return getParentMap().getParent(S); 347218887Sdim } 348218887Sdim 349276479Sdim NodeMapClosure& getNodeResolver() override { return NMC; } 350218887Sdim 351218887Sdim PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S); 352218887Sdim 353226633Sdim PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const { 354226633Sdim return PDC ? PDC->getGenerationScheme() : PathDiagnosticConsumer::Extensive; 355218887Sdim } 356218887Sdim 357218887Sdim bool supportsLogicalOpControlFlow() const { 358218887Sdim return PDC ? PDC->supportsLogicalOpControlFlow() : true; 359218887Sdim } 360218887Sdim}; 361218887Sdim} // end anonymous namespace 362218887Sdim 363218887SdimPathDiagnosticLocation 364226633SdimPathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) { 365251662Sdim if (const Stmt *S = PathDiagnosticLocation::getNextStmt(N)) 366234353Sdim return PathDiagnosticLocation(S, getSourceManager(), LC); 367218887Sdim 368226633Sdim return PathDiagnosticLocation::createDeclEnd(N->getLocationContext(), 369226633Sdim getSourceManager()); 370218887Sdim} 371218887Sdim 372218887SdimPathDiagnosticLocation 373226633SdimPathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os, 374226633Sdim const ExplodedNode *N) { 375218887Sdim 376218887Sdim // Slow, but probably doesn't matter. 377218887Sdim if (os.str().empty()) 378218887Sdim os << ' '; 379218887Sdim 380218887Sdim const PathDiagnosticLocation &Loc = ExecutionContinues(N); 381218887Sdim 382218887Sdim if (Loc.asStmt()) 383218887Sdim os << "Execution continues on line " 384226633Sdim << getSourceManager().getExpansionLineNumber(Loc.asLocation()) 385218887Sdim << '.'; 386218887Sdim else { 387218887Sdim os << "Execution jumps to the end of the "; 388218887Sdim const Decl *D = N->getLocationContext()->getDecl(); 389218887Sdim if (isa<ObjCMethodDecl>(D)) 390218887Sdim os << "method"; 391218887Sdim else if (isa<FunctionDecl>(D)) 392218887Sdim os << "function"; 393218887Sdim else { 394218887Sdim assert(isa<BlockDecl>(D)); 395218887Sdim os << "anonymous block"; 396218887Sdim } 397218887Sdim os << '.'; 398218887Sdim } 399218887Sdim 400218887Sdim return Loc; 401218887Sdim} 402218887Sdim 403261991Sdimstatic const Stmt *getEnclosingParent(const Stmt *S, const ParentMap &PM) { 404218887Sdim if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S))) 405261991Sdim return PM.getParentIgnoreParens(S); 406218887Sdim 407218887Sdim const Stmt *Parent = PM.getParentIgnoreParens(S); 408261991Sdim if (!Parent) 409276479Sdim return nullptr; 410218887Sdim 411261991Sdim switch (Parent->getStmtClass()) { 412261991Sdim case Stmt::ForStmtClass: 413261991Sdim case Stmt::DoStmtClass: 414261991Sdim case Stmt::WhileStmtClass: 415261991Sdim case Stmt::ObjCForCollectionStmtClass: 416261991Sdim case Stmt::CXXForRangeStmtClass: 417261991Sdim return Parent; 418261991Sdim default: 419261991Sdim break; 420261991Sdim } 421218887Sdim 422276479Sdim return nullptr; 423218887Sdim} 424218887Sdim 425261991Sdimstatic PathDiagnosticLocation 426261991SdimgetEnclosingStmtLocation(const Stmt *S, SourceManager &SMgr, const ParentMap &P, 427261991Sdim const LocationContext *LC, bool allowNestedContexts) { 428261991Sdim if (!S) 429261991Sdim return PathDiagnosticLocation(); 430218887Sdim 431261991Sdim while (const Stmt *Parent = getEnclosingParent(S, P)) { 432218887Sdim switch (Parent->getStmtClass()) { 433218887Sdim case Stmt::BinaryOperatorClass: { 434218887Sdim const BinaryOperator *B = cast<BinaryOperator>(Parent); 435218887Sdim if (B->isLogicalOp()) 436261991Sdim return PathDiagnosticLocation(allowNestedContexts ? B : S, SMgr, LC); 437218887Sdim break; 438218887Sdim } 439218887Sdim case Stmt::CompoundStmtClass: 440218887Sdim case Stmt::StmtExprClass: 441226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 442218887Sdim case Stmt::ChooseExprClass: 443218887Sdim // Similar to '?' if we are referring to condition, just have the edge 444218887Sdim // point to the entire choose expression. 445261991Sdim if (allowNestedContexts || cast<ChooseExpr>(Parent)->getCond() == S) 446226633Sdim return PathDiagnosticLocation(Parent, SMgr, LC); 447218887Sdim else 448226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 449218887Sdim case Stmt::BinaryConditionalOperatorClass: 450218887Sdim case Stmt::ConditionalOperatorClass: 451218887Sdim // For '?', if we are referring to condition, just have the edge point 452218887Sdim // to the entire '?' expression. 453261991Sdim if (allowNestedContexts || 454261991Sdim cast<AbstractConditionalOperator>(Parent)->getCond() == S) 455226633Sdim return PathDiagnosticLocation(Parent, SMgr, LC); 456218887Sdim else 457226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 458261991Sdim case Stmt::CXXForRangeStmtClass: 459261991Sdim if (cast<CXXForRangeStmt>(Parent)->getBody() == S) 460261991Sdim return PathDiagnosticLocation(S, SMgr, LC); 461261991Sdim break; 462218887Sdim case Stmt::DoStmtClass: 463226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 464218887Sdim case Stmt::ForStmtClass: 465218887Sdim if (cast<ForStmt>(Parent)->getBody() == S) 466226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 467218887Sdim break; 468218887Sdim case Stmt::IfStmtClass: 469218887Sdim if (cast<IfStmt>(Parent)->getCond() != S) 470226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 471218887Sdim break; 472218887Sdim case Stmt::ObjCForCollectionStmtClass: 473218887Sdim if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S) 474226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 475218887Sdim break; 476218887Sdim case Stmt::WhileStmtClass: 477218887Sdim if (cast<WhileStmt>(Parent)->getCond() != S) 478226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 479218887Sdim break; 480218887Sdim default: 481218887Sdim break; 482218887Sdim } 483218887Sdim 484218887Sdim S = Parent; 485218887Sdim } 486218887Sdim 487218887Sdim assert(S && "Cannot have null Stmt for PathDiagnosticLocation"); 488218887Sdim 489226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 490218887Sdim} 491218887Sdim 492261991SdimPathDiagnosticLocation 493261991SdimPathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { 494261991Sdim assert(S && "Null Stmt passed to getEnclosingStmtLocation"); 495261991Sdim return ::getEnclosingStmtLocation(S, getSourceManager(), getParentMap(), LC, 496261991Sdim /*allowNestedContexts=*/false); 497261991Sdim} 498261991Sdim 499218887Sdim//===----------------------------------------------------------------------===// 500243830Sdim// "Visitors only" path diagnostic generation algorithm. 501243830Sdim//===----------------------------------------------------------------------===// 502280031Sdimstatic bool GenerateVisitorsOnlyPathDiagnostic( 503280031Sdim PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, 504280031Sdim ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors) { 505243830Sdim // All path generation skips the very first node (the error node). 506243830Sdim // This is because there is special handling for the end-of-path note. 507243830Sdim N = N->getFirstPred(); 508243830Sdim if (!N) 509243830Sdim return true; 510243830Sdim 511243830Sdim BugReport *R = PDB.getBugReport(); 512243830Sdim while (const ExplodedNode *Pred = N->getFirstPred()) { 513280031Sdim for (auto &V : visitors) { 514243830Sdim // Visit all the node pairs, but throw the path pieces away. 515280031Sdim PathDiagnosticPiece *Piece = V->VisitNode(N, Pred, PDB, *R); 516243830Sdim delete Piece; 517243830Sdim } 518243830Sdim 519243830Sdim N = Pred; 520243830Sdim } 521243830Sdim 522243830Sdim return R->isValid(); 523243830Sdim} 524243830Sdim 525243830Sdim//===----------------------------------------------------------------------===// 526234353Sdim// "Minimal" path diagnostic generation algorithm. 527218887Sdim//===----------------------------------------------------------------------===// 528234353Sdimtypedef std::pair<PathDiagnosticCallPiece*, const ExplodedNode*> StackDiagPair; 529234353Sdimtypedef SmallVector<StackDiagPair, 6> StackDiagVector; 530218887Sdim 531234353Sdimstatic void updateStackPiecesWithMessage(PathDiagnosticPiece *P, 532234353Sdim StackDiagVector &CallStack) { 533234353Sdim // If the piece contains a special message, add it to all the call 534234353Sdim // pieces on the active stack. 535234353Sdim if (PathDiagnosticEventPiece *ep = 536234353Sdim dyn_cast<PathDiagnosticEventPiece>(P)) { 537218887Sdim 538234353Sdim if (ep->hasCallStackHint()) 539234353Sdim for (StackDiagVector::iterator I = CallStack.begin(), 540234353Sdim E = CallStack.end(); I != E; ++I) { 541234353Sdim PathDiagnosticCallPiece *CP = I->first; 542234353Sdim const ExplodedNode *N = I->second; 543234353Sdim std::string stackMsg = ep->getCallStackMessage(N); 544218887Sdim 545234353Sdim // The last message on the path to final bug is the most important 546234353Sdim // one. Since we traverse the path backwards, do not add the message 547234353Sdim // if one has been previously added. 548234353Sdim if (!CP->hasCallStackMessage()) 549234353Sdim CP->setCallStackMessage(stackMsg); 550234353Sdim } 551218887Sdim } 552218887Sdim} 553218887Sdim 554234353Sdimstatic void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM); 555218887Sdim 556280031Sdimstatic bool GenerateMinimalPathDiagnostic( 557280031Sdim PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, 558280031Sdim LocationContextMap &LCM, 559280031Sdim ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors) { 560218887Sdim 561218887Sdim SourceManager& SMgr = PDB.getSourceManager(); 562234353Sdim const LocationContext *LC = PDB.LC; 563226633Sdim const ExplodedNode *NextNode = N->pred_empty() 564276479Sdim ? nullptr : *(N->pred_begin()); 565234353Sdim 566234353Sdim StackDiagVector CallStack; 567234353Sdim 568218887Sdim while (NextNode) { 569218887Sdim N = NextNode; 570234353Sdim PDB.LC = N->getLocationContext(); 571251662Sdim NextNode = N->getFirstPred(); 572218887Sdim 573218887Sdim ProgramPoint P = N->getLocation(); 574239462Sdim 575243830Sdim do { 576249423Sdim if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) { 577243830Sdim PathDiagnosticCallPiece *C = 578243830Sdim PathDiagnosticCallPiece::construct(N, *CE, SMgr); 579251662Sdim // Record the mapping from call piece to LocationContext. 580251662Sdim LCM[&C->path] = CE->getCalleeContext(); 581243830Sdim PD.getActivePath().push_front(C); 582243830Sdim PD.pushActivePath(&C->path); 583243830Sdim CallStack.push_back(StackDiagPair(C, N)); 584243830Sdim break; 585234353Sdim } 586239462Sdim 587249423Sdim if (Optional<CallEnter> CE = P.getAs<CallEnter>()) { 588243830Sdim // Flush all locations, and pop the active path. 589243830Sdim bool VisitedEntireCall = PD.isWithinCall(); 590243830Sdim PD.popActivePath(); 591243830Sdim 592243830Sdim // Either we just added a bunch of stuff to the top-level path, or 593243830Sdim // we have a previous CallExitEnd. If the former, it means that the 594243830Sdim // path terminated within a function call. We must then take the 595243830Sdim // current contents of the active path and place it within 596243830Sdim // a new PathDiagnosticCallPiece. 597243830Sdim PathDiagnosticCallPiece *C; 598243830Sdim if (VisitedEntireCall) { 599243830Sdim C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); 600243830Sdim } else { 601243830Sdim const Decl *Caller = CE->getLocationContext()->getDecl(); 602243830Sdim C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 603251662Sdim // Record the mapping from call piece to LocationContext. 604251662Sdim LCM[&C->path] = CE->getCalleeContext(); 605243830Sdim } 606243830Sdim 607243830Sdim C->setCallee(*CE, SMgr); 608243830Sdim if (!CallStack.empty()) { 609243830Sdim assert(CallStack.back().first == C); 610243830Sdim CallStack.pop_back(); 611243830Sdim } 612243830Sdim break; 613234353Sdim } 614218887Sdim 615249423Sdim if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) { 616243830Sdim const CFGBlock *Src = BE->getSrc(); 617243830Sdim const CFGBlock *Dst = BE->getDst(); 618243830Sdim const Stmt *T = Src->getTerminator(); 619218887Sdim 620243830Sdim if (!T) 621243830Sdim break; 622218887Sdim 623243830Sdim PathDiagnosticLocation Start = 624243830Sdim PathDiagnosticLocation::createBegin(T, SMgr, 625243830Sdim N->getLocationContext()); 626218887Sdim 627243830Sdim switch (T->getStmtClass()) { 628218887Sdim default: 629218887Sdim break; 630218887Sdim 631218887Sdim case Stmt::GotoStmtClass: 632218887Sdim case Stmt::IndirectGotoStmtClass: { 633251662Sdim const Stmt *S = PathDiagnosticLocation::getNextStmt(N); 634218887Sdim 635218887Sdim if (!S) 636243830Sdim break; 637218887Sdim 638218887Sdim std::string sbuf; 639218887Sdim llvm::raw_string_ostream os(sbuf); 640218887Sdim const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S); 641218887Sdim 642218887Sdim os << "Control jumps to line " 643243830Sdim << End.asLocation().getExpansionLineNumber(); 644243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 645243830Sdim Start, End, os.str())); 646218887Sdim break; 647218887Sdim } 648218887Sdim 649218887Sdim case Stmt::SwitchStmtClass: { 650218887Sdim // Figure out what case arm we took. 651218887Sdim std::string sbuf; 652218887Sdim llvm::raw_string_ostream os(sbuf); 653218887Sdim 654226633Sdim if (const Stmt *S = Dst->getLabel()) { 655226633Sdim PathDiagnosticLocation End(S, SMgr, LC); 656218887Sdim 657218887Sdim switch (S->getStmtClass()) { 658243830Sdim default: 659243830Sdim os << "No cases match in the switch statement. " 660243830Sdim "Control jumps to line " 661243830Sdim << End.asLocation().getExpansionLineNumber(); 662243830Sdim break; 663243830Sdim case Stmt::DefaultStmtClass: 664243830Sdim os << "Control jumps to the 'default' case at line " 665243830Sdim << End.asLocation().getExpansionLineNumber(); 666243830Sdim break; 667218887Sdim 668243830Sdim case Stmt::CaseStmtClass: { 669243830Sdim os << "Control jumps to 'case "; 670243830Sdim const CaseStmt *Case = cast<CaseStmt>(S); 671243830Sdim const Expr *LHS = Case->getLHS()->IgnoreParenCasts(); 672218887Sdim 673243830Sdim // Determine if it is an enum. 674243830Sdim bool GetRawInt = true; 675218887Sdim 676243830Sdim if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) { 677243830Sdim // FIXME: Maybe this should be an assertion. Are there cases 678243830Sdim // were it is not an EnumConstantDecl? 679243830Sdim const EnumConstantDecl *D = 680218887Sdim dyn_cast<EnumConstantDecl>(DR->getDecl()); 681218887Sdim 682243830Sdim if (D) { 683243830Sdim GetRawInt = false; 684243830Sdim os << *D; 685218887Sdim } 686243830Sdim } 687218887Sdim 688243830Sdim if (GetRawInt) 689243830Sdim os << LHS->EvaluateKnownConstInt(PDB.getASTContext()); 690218887Sdim 691243830Sdim os << ":' at line " 692243830Sdim << End.asLocation().getExpansionLineNumber(); 693243830Sdim break; 694218887Sdim } 695243830Sdim } 696243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 697243830Sdim Start, End, os.str())); 698218887Sdim } 699218887Sdim else { 700218887Sdim os << "'Default' branch taken. "; 701218887Sdim const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N); 702243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 703243830Sdim Start, End, os.str())); 704218887Sdim } 705218887Sdim 706218887Sdim break; 707218887Sdim } 708218887Sdim 709218887Sdim case Stmt::BreakStmtClass: 710218887Sdim case Stmt::ContinueStmtClass: { 711218887Sdim std::string sbuf; 712218887Sdim llvm::raw_string_ostream os(sbuf); 713218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 714243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 715243830Sdim Start, End, os.str())); 716218887Sdim break; 717218887Sdim } 718218887Sdim 719243830Sdim // Determine control-flow for ternary '?'. 720218887Sdim case Stmt::BinaryConditionalOperatorClass: 721218887Sdim case Stmt::ConditionalOperatorClass: { 722218887Sdim std::string sbuf; 723218887Sdim llvm::raw_string_ostream os(sbuf); 724218887Sdim os << "'?' condition is "; 725218887Sdim 726218887Sdim if (*(Src->succ_begin()+1) == Dst) 727218887Sdim os << "false"; 728218887Sdim else 729218887Sdim os << "true"; 730218887Sdim 731218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 732218887Sdim 733218887Sdim if (const Stmt *S = End.asStmt()) 734218887Sdim End = PDB.getEnclosingStmtLocation(S); 735218887Sdim 736243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 737243830Sdim Start, End, os.str())); 738218887Sdim break; 739218887Sdim } 740218887Sdim 741243830Sdim // Determine control-flow for short-circuited '&&' and '||'. 742218887Sdim case Stmt::BinaryOperatorClass: { 743218887Sdim if (!PDB.supportsLogicalOpControlFlow()) 744218887Sdim break; 745218887Sdim 746218887Sdim const BinaryOperator *B = cast<BinaryOperator>(T); 747218887Sdim std::string sbuf; 748218887Sdim llvm::raw_string_ostream os(sbuf); 749218887Sdim os << "Left side of '"; 750218887Sdim 751218887Sdim if (B->getOpcode() == BO_LAnd) { 752218887Sdim os << "&&" << "' is "; 753218887Sdim 754218887Sdim if (*(Src->succ_begin()+1) == Dst) { 755218887Sdim os << "false"; 756226633Sdim PathDiagnosticLocation End(B->getLHS(), SMgr, LC); 757226633Sdim PathDiagnosticLocation Start = 758243830Sdim PathDiagnosticLocation::createOperatorLoc(B, SMgr); 759243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 760243830Sdim Start, End, os.str())); 761218887Sdim } 762218887Sdim else { 763218887Sdim os << "true"; 764226633Sdim PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); 765218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 766243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 767243830Sdim Start, End, os.str())); 768218887Sdim } 769218887Sdim } 770218887Sdim else { 771218887Sdim assert(B->getOpcode() == BO_LOr); 772218887Sdim os << "||" << "' is "; 773218887Sdim 774218887Sdim if (*(Src->succ_begin()+1) == Dst) { 775218887Sdim os << "false"; 776226633Sdim PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); 777218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 778243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 779243830Sdim Start, End, os.str())); 780218887Sdim } 781218887Sdim else { 782218887Sdim os << "true"; 783226633Sdim PathDiagnosticLocation End(B->getLHS(), SMgr, LC); 784226633Sdim PathDiagnosticLocation Start = 785243830Sdim PathDiagnosticLocation::createOperatorLoc(B, SMgr); 786243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 787243830Sdim Start, End, os.str())); 788218887Sdim } 789218887Sdim } 790218887Sdim 791218887Sdim break; 792218887Sdim } 793218887Sdim 794218887Sdim case Stmt::DoStmtClass: { 795218887Sdim if (*(Src->succ_begin()) == Dst) { 796218887Sdim std::string sbuf; 797218887Sdim llvm::raw_string_ostream os(sbuf); 798218887Sdim 799218887Sdim os << "Loop condition is true. "; 800218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 801218887Sdim 802218887Sdim if (const Stmt *S = End.asStmt()) 803218887Sdim End = PDB.getEnclosingStmtLocation(S); 804218887Sdim 805243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 806243830Sdim Start, End, os.str())); 807218887Sdim } 808218887Sdim else { 809218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 810218887Sdim 811218887Sdim if (const Stmt *S = End.asStmt()) 812218887Sdim End = PDB.getEnclosingStmtLocation(S); 813218887Sdim 814243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 815243830Sdim Start, End, "Loop condition is false. Exiting loop")); 816218887Sdim } 817218887Sdim 818218887Sdim break; 819218887Sdim } 820218887Sdim 821218887Sdim case Stmt::WhileStmtClass: 822218887Sdim case Stmt::ForStmtClass: { 823218887Sdim if (*(Src->succ_begin()+1) == Dst) { 824218887Sdim std::string sbuf; 825218887Sdim llvm::raw_string_ostream os(sbuf); 826218887Sdim 827218887Sdim os << "Loop condition is false. "; 828218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 829218887Sdim if (const Stmt *S = End.asStmt()) 830218887Sdim End = PDB.getEnclosingStmtLocation(S); 831218887Sdim 832243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 833243830Sdim Start, End, os.str())); 834218887Sdim } 835218887Sdim else { 836218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 837218887Sdim if (const Stmt *S = End.asStmt()) 838218887Sdim End = PDB.getEnclosingStmtLocation(S); 839218887Sdim 840243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 841243830Sdim Start, End, "Loop condition is true. Entering loop body")); 842218887Sdim } 843218887Sdim 844218887Sdim break; 845218887Sdim } 846218887Sdim 847218887Sdim case Stmt::IfStmtClass: { 848218887Sdim PathDiagnosticLocation End = PDB.ExecutionContinues(N); 849218887Sdim 850218887Sdim if (const Stmt *S = End.asStmt()) 851218887Sdim End = PDB.getEnclosingStmtLocation(S); 852218887Sdim 853218887Sdim if (*(Src->succ_begin()+1) == Dst) 854243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 855243830Sdim Start, End, "Taking false branch")); 856218887Sdim else 857243830Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 858243830Sdim Start, End, "Taking true branch")); 859218887Sdim 860218887Sdim break; 861218887Sdim } 862243830Sdim } 863218887Sdim } 864243830Sdim } while(0); 865218887Sdim 866218887Sdim if (NextNode) { 867226633Sdim // Add diagnostic pieces from custom visitors. 868226633Sdim BugReport *R = PDB.getBugReport(); 869280031Sdim for (auto &V : visitors) { 870280031Sdim if (PathDiagnosticPiece *p = V->VisitNode(N, NextNode, PDB, *R)) { 871234353Sdim PD.getActivePath().push_front(p); 872234353Sdim updateStackPiecesWithMessage(p, CallStack); 873234353Sdim } 874218887Sdim } 875218887Sdim } 876218887Sdim } 877218887Sdim 878243830Sdim if (!PDB.getBugReport()->isValid()) 879243830Sdim return false; 880243830Sdim 881218887Sdim // After constructing the full PathDiagnostic, do a pass over it to compact 882218887Sdim // PathDiagnosticPieces that occur within a macro. 883234353Sdim CompactPathDiagnostic(PD.getMutablePieces(), PDB.getSourceManager()); 884243830Sdim return true; 885218887Sdim} 886218887Sdim 887218887Sdim//===----------------------------------------------------------------------===// 888218887Sdim// "Extensive" PathDiagnostic generation. 889218887Sdim//===----------------------------------------------------------------------===// 890218887Sdim 891218887Sdimstatic bool IsControlFlowExpr(const Stmt *S) { 892218887Sdim const Expr *E = dyn_cast<Expr>(S); 893218887Sdim 894218887Sdim if (!E) 895218887Sdim return false; 896218887Sdim 897218887Sdim E = E->IgnoreParenCasts(); 898218887Sdim 899218887Sdim if (isa<AbstractConditionalOperator>(E)) 900218887Sdim return true; 901218887Sdim 902218887Sdim if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E)) 903218887Sdim if (B->isLogicalOp()) 904218887Sdim return true; 905218887Sdim 906218887Sdim return false; 907218887Sdim} 908218887Sdim 909218887Sdimnamespace { 910218887Sdimclass ContextLocation : public PathDiagnosticLocation { 911218887Sdim bool IsDead; 912218887Sdimpublic: 913218887Sdim ContextLocation(const PathDiagnosticLocation &L, bool isdead = false) 914218887Sdim : PathDiagnosticLocation(L), IsDead(isdead) {} 915218887Sdim 916218887Sdim void markDead() { IsDead = true; } 917218887Sdim bool isDead() const { return IsDead; } 918218887Sdim}; 919218887Sdim 920251662Sdimstatic PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L, 921251662Sdim const LocationContext *LC, 922251662Sdim bool firstCharOnly = false) { 923251662Sdim if (const Stmt *S = L.asStmt()) { 924251662Sdim const Stmt *Original = S; 925251662Sdim while (1) { 926251662Sdim // Adjust the location for some expressions that are best referenced 927251662Sdim // by one of their subexpressions. 928251662Sdim switch (S->getStmtClass()) { 929251662Sdim default: 930251662Sdim break; 931251662Sdim case Stmt::ParenExprClass: 932251662Sdim case Stmt::GenericSelectionExprClass: 933251662Sdim S = cast<Expr>(S)->IgnoreParens(); 934251662Sdim firstCharOnly = true; 935251662Sdim continue; 936251662Sdim case Stmt::BinaryConditionalOperatorClass: 937251662Sdim case Stmt::ConditionalOperatorClass: 938251662Sdim S = cast<AbstractConditionalOperator>(S)->getCond(); 939251662Sdim firstCharOnly = true; 940251662Sdim continue; 941251662Sdim case Stmt::ChooseExprClass: 942251662Sdim S = cast<ChooseExpr>(S)->getCond(); 943251662Sdim firstCharOnly = true; 944251662Sdim continue; 945251662Sdim case Stmt::BinaryOperatorClass: 946251662Sdim S = cast<BinaryOperator>(S)->getLHS(); 947251662Sdim firstCharOnly = true; 948251662Sdim continue; 949251662Sdim } 950251662Sdim 951251662Sdim break; 952251662Sdim } 953251662Sdim 954251662Sdim if (S != Original) 955251662Sdim L = PathDiagnosticLocation(S, L.getManager(), LC); 956251662Sdim } 957251662Sdim 958251662Sdim if (firstCharOnly) 959251662Sdim L = PathDiagnosticLocation::createSingleLocation(L); 960251662Sdim 961251662Sdim return L; 962251662Sdim} 963251662Sdim 964218887Sdimclass EdgeBuilder { 965218887Sdim std::vector<ContextLocation> CLocs; 966218887Sdim typedef std::vector<ContextLocation>::iterator iterator; 967218887Sdim PathDiagnostic &PD; 968218887Sdim PathDiagnosticBuilder &PDB; 969218887Sdim PathDiagnosticLocation PrevLoc; 970218887Sdim 971218887Sdim bool IsConsumedExpr(const PathDiagnosticLocation &L); 972218887Sdim 973218887Sdim bool containsLocation(const PathDiagnosticLocation &Container, 974218887Sdim const PathDiagnosticLocation &Containee); 975218887Sdim 976218887Sdim PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L); 977218887Sdim 978218887Sdim 979218887Sdim 980218887Sdim void popLocation() { 981218887Sdim if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) { 982218887Sdim // For contexts, we only one the first character as the range. 983251662Sdim rawAddEdge(cleanUpLocation(CLocs.back(), PDB.LC, true)); 984218887Sdim } 985218887Sdim CLocs.pop_back(); 986218887Sdim } 987218887Sdim 988218887Sdimpublic: 989218887Sdim EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb) 990218887Sdim : PD(pd), PDB(pdb) { 991218887Sdim 992218887Sdim // If the PathDiagnostic already has pieces, add the enclosing statement 993218887Sdim // of the first piece as a context as well. 994234353Sdim if (!PD.path.empty()) { 995234353Sdim PrevLoc = (*PD.path.begin())->getLocation(); 996218887Sdim 997218887Sdim if (const Stmt *S = PrevLoc.asStmt()) 998218887Sdim addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 999218887Sdim } 1000218887Sdim } 1001218887Sdim 1002218887Sdim ~EdgeBuilder() { 1003218887Sdim while (!CLocs.empty()) popLocation(); 1004226633Sdim 1005218887Sdim // Finally, add an initial edge from the start location of the first 1006218887Sdim // statement (if it doesn't already exist). 1007226633Sdim PathDiagnosticLocation L = PathDiagnosticLocation::createDeclBegin( 1008234353Sdim PDB.LC, 1009226633Sdim PDB.getSourceManager()); 1010226633Sdim if (L.isValid()) 1011226633Sdim rawAddEdge(L); 1012218887Sdim } 1013218887Sdim 1014234353Sdim void flushLocations() { 1015234353Sdim while (!CLocs.empty()) 1016234353Sdim popLocation(); 1017234353Sdim PrevLoc = PathDiagnosticLocation(); 1018234353Sdim } 1019234353Sdim 1020251662Sdim void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false, 1021251662Sdim bool IsPostJump = false); 1022218887Sdim 1023218887Sdim void rawAddEdge(PathDiagnosticLocation NewLoc); 1024218887Sdim 1025218887Sdim void addContext(const Stmt *S); 1026239462Sdim void addContext(const PathDiagnosticLocation &L); 1027218887Sdim void addExtendedContext(const Stmt *S); 1028218887Sdim}; 1029218887Sdim} // end anonymous namespace 1030218887Sdim 1031218887Sdim 1032218887SdimPathDiagnosticLocation 1033218887SdimEdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) { 1034218887Sdim if (const Stmt *S = L.asStmt()) { 1035218887Sdim if (IsControlFlowExpr(S)) 1036218887Sdim return L; 1037218887Sdim 1038218887Sdim return PDB.getEnclosingStmtLocation(S); 1039218887Sdim } 1040218887Sdim 1041218887Sdim return L; 1042218887Sdim} 1043218887Sdim 1044218887Sdimbool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container, 1045218887Sdim const PathDiagnosticLocation &Containee) { 1046218887Sdim 1047218887Sdim if (Container == Containee) 1048218887Sdim return true; 1049218887Sdim 1050218887Sdim if (Container.asDecl()) 1051218887Sdim return true; 1052218887Sdim 1053218887Sdim if (const Stmt *S = Containee.asStmt()) 1054218887Sdim if (const Stmt *ContainerS = Container.asStmt()) { 1055218887Sdim while (S) { 1056218887Sdim if (S == ContainerS) 1057218887Sdim return true; 1058218887Sdim S = PDB.getParent(S); 1059218887Sdim } 1060218887Sdim return false; 1061218887Sdim } 1062218887Sdim 1063218887Sdim // Less accurate: compare using source ranges. 1064218887Sdim SourceRange ContainerR = Container.asRange(); 1065218887Sdim SourceRange ContaineeR = Containee.asRange(); 1066218887Sdim 1067218887Sdim SourceManager &SM = PDB.getSourceManager(); 1068226633Sdim SourceLocation ContainerRBeg = SM.getExpansionLoc(ContainerR.getBegin()); 1069226633Sdim SourceLocation ContainerREnd = SM.getExpansionLoc(ContainerR.getEnd()); 1070226633Sdim SourceLocation ContaineeRBeg = SM.getExpansionLoc(ContaineeR.getBegin()); 1071226633Sdim SourceLocation ContaineeREnd = SM.getExpansionLoc(ContaineeR.getEnd()); 1072218887Sdim 1073226633Sdim unsigned ContainerBegLine = SM.getExpansionLineNumber(ContainerRBeg); 1074226633Sdim unsigned ContainerEndLine = SM.getExpansionLineNumber(ContainerREnd); 1075226633Sdim unsigned ContaineeBegLine = SM.getExpansionLineNumber(ContaineeRBeg); 1076226633Sdim unsigned ContaineeEndLine = SM.getExpansionLineNumber(ContaineeREnd); 1077218887Sdim 1078218887Sdim assert(ContainerBegLine <= ContainerEndLine); 1079218887Sdim assert(ContaineeBegLine <= ContaineeEndLine); 1080218887Sdim 1081218887Sdim return (ContainerBegLine <= ContaineeBegLine && 1082218887Sdim ContainerEndLine >= ContaineeEndLine && 1083218887Sdim (ContainerBegLine != ContaineeBegLine || 1084226633Sdim SM.getExpansionColumnNumber(ContainerRBeg) <= 1085226633Sdim SM.getExpansionColumnNumber(ContaineeRBeg)) && 1086218887Sdim (ContainerEndLine != ContaineeEndLine || 1087226633Sdim SM.getExpansionColumnNumber(ContainerREnd) >= 1088234353Sdim SM.getExpansionColumnNumber(ContaineeREnd))); 1089218887Sdim} 1090218887Sdim 1091218887Sdimvoid EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) { 1092218887Sdim if (!PrevLoc.isValid()) { 1093218887Sdim PrevLoc = NewLoc; 1094218887Sdim return; 1095218887Sdim } 1096218887Sdim 1097251662Sdim const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc, PDB.LC); 1098251662Sdim const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc, PDB.LC); 1099218887Sdim 1100243830Sdim if (PrevLocClean.asLocation().isInvalid()) { 1101243830Sdim PrevLoc = NewLoc; 1102243830Sdim return; 1103243830Sdim } 1104243830Sdim 1105218887Sdim if (NewLocClean.asLocation() == PrevLocClean.asLocation()) 1106218887Sdim return; 1107218887Sdim 1108218887Sdim // FIXME: Ignore intra-macro edges for now. 1109226633Sdim if (NewLocClean.asLocation().getExpansionLoc() == 1110226633Sdim PrevLocClean.asLocation().getExpansionLoc()) 1111218887Sdim return; 1112218887Sdim 1113234353Sdim PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean)); 1114218887Sdim PrevLoc = NewLoc; 1115218887Sdim} 1116218887Sdim 1117251662Sdimvoid EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd, 1118251662Sdim bool IsPostJump) { 1119218887Sdim 1120218887Sdim if (!alwaysAdd && NewLoc.asLocation().isMacroID()) 1121218887Sdim return; 1122218887Sdim 1123218887Sdim const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc); 1124218887Sdim 1125218887Sdim while (!CLocs.empty()) { 1126218887Sdim ContextLocation &TopContextLoc = CLocs.back(); 1127218887Sdim 1128218887Sdim // Is the top location context the same as the one for the new location? 1129218887Sdim if (TopContextLoc == CLoc) { 1130218887Sdim if (alwaysAdd) { 1131251662Sdim if (IsConsumedExpr(TopContextLoc)) 1132251662Sdim TopContextLoc.markDead(); 1133218887Sdim 1134218887Sdim rawAddEdge(NewLoc); 1135218887Sdim } 1136218887Sdim 1137251662Sdim if (IsPostJump) 1138251662Sdim TopContextLoc.markDead(); 1139218887Sdim return; 1140218887Sdim } 1141218887Sdim 1142218887Sdim if (containsLocation(TopContextLoc, CLoc)) { 1143218887Sdim if (alwaysAdd) { 1144218887Sdim rawAddEdge(NewLoc); 1145218887Sdim 1146251662Sdim if (IsConsumedExpr(CLoc)) { 1147251662Sdim CLocs.push_back(ContextLocation(CLoc, /*IsDead=*/true)); 1148218887Sdim return; 1149218887Sdim } 1150218887Sdim } 1151218887Sdim 1152251662Sdim CLocs.push_back(ContextLocation(CLoc, /*IsDead=*/IsPostJump)); 1153218887Sdim return; 1154218887Sdim } 1155218887Sdim 1156218887Sdim // Context does not contain the location. Flush it. 1157218887Sdim popLocation(); 1158218887Sdim } 1159218887Sdim 1160218887Sdim // If we reach here, there is no enclosing context. Just add the edge. 1161218887Sdim rawAddEdge(NewLoc); 1162218887Sdim} 1163218887Sdim 1164218887Sdimbool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) { 1165218887Sdim if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt())) 1166218887Sdim return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X); 1167218887Sdim 1168218887Sdim return false; 1169218887Sdim} 1170218887Sdim 1171218887Sdimvoid EdgeBuilder::addExtendedContext(const Stmt *S) { 1172218887Sdim if (!S) 1173218887Sdim return; 1174218887Sdim 1175218887Sdim const Stmt *Parent = PDB.getParent(S); 1176218887Sdim while (Parent) { 1177218887Sdim if (isa<CompoundStmt>(Parent)) 1178218887Sdim Parent = PDB.getParent(Parent); 1179218887Sdim else 1180218887Sdim break; 1181218887Sdim } 1182218887Sdim 1183218887Sdim if (Parent) { 1184218887Sdim switch (Parent->getStmtClass()) { 1185218887Sdim case Stmt::DoStmtClass: 1186218887Sdim case Stmt::ObjCAtSynchronizedStmtClass: 1187218887Sdim addContext(Parent); 1188218887Sdim default: 1189218887Sdim break; 1190218887Sdim } 1191218887Sdim } 1192218887Sdim 1193218887Sdim addContext(S); 1194218887Sdim} 1195218887Sdim 1196218887Sdimvoid EdgeBuilder::addContext(const Stmt *S) { 1197218887Sdim if (!S) 1198218887Sdim return; 1199218887Sdim 1200234353Sdim PathDiagnosticLocation L(S, PDB.getSourceManager(), PDB.LC); 1201239462Sdim addContext(L); 1202239462Sdim} 1203218887Sdim 1204239462Sdimvoid EdgeBuilder::addContext(const PathDiagnosticLocation &L) { 1205218887Sdim while (!CLocs.empty()) { 1206218887Sdim const PathDiagnosticLocation &TopContextLoc = CLocs.back(); 1207218887Sdim 1208218887Sdim // Is the top location context the same as the one for the new location? 1209218887Sdim if (TopContextLoc == L) 1210218887Sdim return; 1211218887Sdim 1212218887Sdim if (containsLocation(TopContextLoc, L)) { 1213218887Sdim CLocs.push_back(L); 1214218887Sdim return; 1215218887Sdim } 1216218887Sdim 1217218887Sdim // Context does not contain the location. Flush it. 1218218887Sdim popLocation(); 1219218887Sdim } 1220218887Sdim 1221218887Sdim CLocs.push_back(L); 1222218887Sdim} 1223218887Sdim 1224239462Sdim// Cone-of-influence: support the reverse propagation of "interesting" symbols 1225239462Sdim// and values by tracing interesting calculations backwards through evaluated 1226239462Sdim// expressions along a path. This is probably overly complicated, but the idea 1227239462Sdim// is that if an expression computed an "interesting" value, the child 1228239462Sdim// expressions are are also likely to be "interesting" as well (which then 1229239462Sdim// propagates to the values they in turn compute). This reverse propagation 1230239462Sdim// is needed to track interesting correlations across function call boundaries, 1231239462Sdim// where formal arguments bind to actual arguments, etc. This is also needed 1232239462Sdim// because the constraint solver sometimes simplifies certain symbolic values 1233239462Sdim// into constants when appropriate, and this complicates reasoning about 1234239462Sdim// interesting values. 1235239462Sdimtypedef llvm::DenseSet<const Expr *> InterestingExprs; 1236239462Sdim 1237239462Sdimstatic void reversePropagateIntererstingSymbols(BugReport &R, 1238239462Sdim InterestingExprs &IE, 1239239462Sdim const ProgramState *State, 1240239462Sdim const Expr *Ex, 1241239462Sdim const LocationContext *LCtx) { 1242239462Sdim SVal V = State->getSVal(Ex, LCtx); 1243239462Sdim if (!(R.isInteresting(V) || IE.count(Ex))) 1244239462Sdim return; 1245239462Sdim 1246239462Sdim switch (Ex->getStmtClass()) { 1247239462Sdim default: 1248239462Sdim if (!isa<CastExpr>(Ex)) 1249239462Sdim break; 1250239462Sdim // Fall through. 1251239462Sdim case Stmt::BinaryOperatorClass: 1252239462Sdim case Stmt::UnaryOperatorClass: { 1253239462Sdim for (Stmt::const_child_iterator CI = Ex->child_begin(), 1254239462Sdim CE = Ex->child_end(); 1255239462Sdim CI != CE; ++CI) { 1256239462Sdim if (const Expr *child = dyn_cast_or_null<Expr>(*CI)) { 1257239462Sdim IE.insert(child); 1258239462Sdim SVal ChildV = State->getSVal(child, LCtx); 1259239462Sdim R.markInteresting(ChildV); 1260239462Sdim } 1261239462Sdim } 1262276479Sdim break; 1263239462Sdim } 1264239462Sdim } 1265239462Sdim 1266239462Sdim R.markInteresting(V); 1267239462Sdim} 1268239462Sdim 1269239462Sdimstatic void reversePropagateInterestingSymbols(BugReport &R, 1270239462Sdim InterestingExprs &IE, 1271239462Sdim const ProgramState *State, 1272239462Sdim const LocationContext *CalleeCtx, 1273239462Sdim const LocationContext *CallerCtx) 1274239462Sdim{ 1275239462Sdim // FIXME: Handle non-CallExpr-based CallEvents. 1276239462Sdim const StackFrameContext *Callee = CalleeCtx->getCurrentStackFrame(); 1277239462Sdim const Stmt *CallSite = Callee->getCallSite(); 1278239462Sdim if (const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite)) { 1279239462Sdim if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CalleeCtx->getDecl())) { 1280239462Sdim FunctionDecl::param_const_iterator PI = FD->param_begin(), 1281239462Sdim PE = FD->param_end(); 1282239462Sdim CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end(); 1283239462Sdim for (; AI != AE && PI != PE; ++AI, ++PI) { 1284239462Sdim if (const Expr *ArgE = *AI) { 1285239462Sdim if (const ParmVarDecl *PD = *PI) { 1286239462Sdim Loc LV = State->getLValue(PD, CalleeCtx); 1287239462Sdim if (R.isInteresting(LV) || R.isInteresting(State->getRawSVal(LV))) 1288239462Sdim IE.insert(ArgE); 1289239462Sdim } 1290239462Sdim } 1291239462Sdim } 1292239462Sdim } 1293239462Sdim } 1294239462Sdim} 1295249423Sdim 1296249423Sdim//===----------------------------------------------------------------------===// 1297249423Sdim// Functions for determining if a loop was executed 0 times. 1298249423Sdim//===----------------------------------------------------------------------===// 1299249423Sdim 1300261991Sdimstatic bool isLoop(const Stmt *Term) { 1301249423Sdim switch (Term->getStmtClass()) { 1302249423Sdim case Stmt::ForStmtClass: 1303249423Sdim case Stmt::WhileStmtClass: 1304249423Sdim case Stmt::ObjCForCollectionStmtClass: 1305261991Sdim case Stmt::CXXForRangeStmtClass: 1306261991Sdim return true; 1307249423Sdim default: 1308249423Sdim // Note that we intentionally do not include do..while here. 1309249423Sdim return false; 1310249423Sdim } 1311261991Sdim} 1312249423Sdim 1313261991Sdimstatic bool isJumpToFalseBranch(const BlockEdge *BE) { 1314249423Sdim const CFGBlock *Src = BE->getSrc(); 1315249423Sdim assert(Src->succ_size() == 2); 1316249423Sdim return (*(Src->succ_begin()+1) == BE->getDst()); 1317249423Sdim} 1318249423Sdim 1319261991Sdim/// Return true if the terminator is a loop and the destination is the 1320261991Sdim/// false branch. 1321261991Sdimstatic bool isLoopJumpPastBody(const Stmt *Term, const BlockEdge *BE) { 1322261991Sdim if (!isLoop(Term)) 1323261991Sdim return false; 1324261991Sdim 1325261991Sdim // Did we take the false branch? 1326261991Sdim return isJumpToFalseBranch(BE); 1327261991Sdim} 1328261991Sdim 1329249423Sdimstatic bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS) { 1330249423Sdim while (SubS) { 1331249423Sdim if (SubS == S) 1332249423Sdim return true; 1333249423Sdim SubS = PM.getParent(SubS); 1334249423Sdim } 1335249423Sdim return false; 1336249423Sdim} 1337249423Sdim 1338249423Sdimstatic const Stmt *getStmtBeforeCond(ParentMap &PM, const Stmt *Term, 1339249423Sdim const ExplodedNode *N) { 1340249423Sdim while (N) { 1341249423Sdim Optional<StmtPoint> SP = N->getLocation().getAs<StmtPoint>(); 1342249423Sdim if (SP) { 1343249423Sdim const Stmt *S = SP->getStmt(); 1344249423Sdim if (!isContainedByStmt(PM, Term, S)) 1345249423Sdim return S; 1346249423Sdim } 1347251662Sdim N = N->getFirstPred(); 1348249423Sdim } 1349276479Sdim return nullptr; 1350249423Sdim} 1351249423Sdim 1352249423Sdimstatic bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term) { 1353276479Sdim const Stmt *LoopBody = nullptr; 1354249423Sdim switch (Term->getStmtClass()) { 1355261991Sdim case Stmt::CXXForRangeStmtClass: { 1356261991Sdim const CXXForRangeStmt *FR = cast<CXXForRangeStmt>(Term); 1357261991Sdim if (isContainedByStmt(PM, FR->getInc(), S)) 1358261991Sdim return true; 1359261991Sdim if (isContainedByStmt(PM, FR->getLoopVarStmt(), S)) 1360261991Sdim return true; 1361261991Sdim LoopBody = FR->getBody(); 1362261991Sdim break; 1363261991Sdim } 1364249423Sdim case Stmt::ForStmtClass: { 1365249423Sdim const ForStmt *FS = cast<ForStmt>(Term); 1366249423Sdim if (isContainedByStmt(PM, FS->getInc(), S)) 1367249423Sdim return true; 1368249423Sdim LoopBody = FS->getBody(); 1369249423Sdim break; 1370249423Sdim } 1371249423Sdim case Stmt::ObjCForCollectionStmtClass: { 1372249423Sdim const ObjCForCollectionStmt *FC = cast<ObjCForCollectionStmt>(Term); 1373249423Sdim LoopBody = FC->getBody(); 1374249423Sdim break; 1375249423Sdim } 1376249423Sdim case Stmt::WhileStmtClass: 1377249423Sdim LoopBody = cast<WhileStmt>(Term)->getBody(); 1378249423Sdim break; 1379249423Sdim default: 1380249423Sdim return false; 1381249423Sdim } 1382249423Sdim return isContainedByStmt(PM, LoopBody, S); 1383249423Sdim} 1384249423Sdim 1385249423Sdim//===----------------------------------------------------------------------===// 1386249423Sdim// Top-level logic for generating extensive path diagnostics. 1387249423Sdim//===----------------------------------------------------------------------===// 1388249423Sdim 1389280031Sdimstatic bool GenerateExtensivePathDiagnostic( 1390280031Sdim PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, 1391280031Sdim LocationContextMap &LCM, 1392280031Sdim ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors) { 1393218887Sdim EdgeBuilder EB(PD, PDB); 1394226633Sdim const SourceManager& SM = PDB.getSourceManager(); 1395234353Sdim StackDiagVector CallStack; 1396239462Sdim InterestingExprs IE; 1397218887Sdim 1398276479Sdim const ExplodedNode *NextNode = N->pred_empty() ? nullptr : *(N->pred_begin()); 1399218887Sdim while (NextNode) { 1400218887Sdim N = NextNode; 1401251662Sdim NextNode = N->getFirstPred(); 1402218887Sdim ProgramPoint P = N->getLocation(); 1403218887Sdim 1404218887Sdim do { 1405249423Sdim if (Optional<PostStmt> PS = P.getAs<PostStmt>()) { 1406239462Sdim if (const Expr *Ex = PS->getStmtAs<Expr>()) 1407239462Sdim reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1408276479Sdim N->getState().get(), Ex, 1409239462Sdim N->getLocationContext()); 1410239462Sdim } 1411239462Sdim 1412249423Sdim if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) { 1413239462Sdim const Stmt *S = CE->getCalleeContext()->getCallSite(); 1414239462Sdim if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) { 1415239462Sdim reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1416276479Sdim N->getState().get(), Ex, 1417239462Sdim N->getLocationContext()); 1418239462Sdim } 1419239462Sdim 1420234353Sdim PathDiagnosticCallPiece *C = 1421234353Sdim PathDiagnosticCallPiece::construct(N, *CE, SM); 1422251662Sdim LCM[&C->path] = CE->getCalleeContext(); 1423239462Sdim 1424251662Sdim EB.addEdge(C->callReturn, /*AlwaysAdd=*/true, /*IsPostJump=*/true); 1425239462Sdim EB.flushLocations(); 1426239462Sdim 1427234353Sdim PD.getActivePath().push_front(C); 1428234353Sdim PD.pushActivePath(&C->path); 1429234353Sdim CallStack.push_back(StackDiagPair(C, N)); 1430234353Sdim break; 1431234353Sdim } 1432234353Sdim 1433234353Sdim // Pop the call hierarchy if we are done walking the contents 1434234353Sdim // of a function call. 1435249423Sdim if (Optional<CallEnter> CE = P.getAs<CallEnter>()) { 1436234353Sdim // Add an edge to the start of the function. 1437234353Sdim const Decl *D = CE->getCalleeContext()->getDecl(); 1438234353Sdim PathDiagnosticLocation pos = 1439234353Sdim PathDiagnosticLocation::createBegin(D, SM); 1440234353Sdim EB.addEdge(pos); 1441234353Sdim 1442234353Sdim // Flush all locations, and pop the active path. 1443239462Sdim bool VisitedEntireCall = PD.isWithinCall(); 1444234353Sdim EB.flushLocations(); 1445234353Sdim PD.popActivePath(); 1446234353Sdim PDB.LC = N->getLocationContext(); 1447234353Sdim 1448239462Sdim // Either we just added a bunch of stuff to the top-level path, or 1449239462Sdim // we have a previous CallExitEnd. If the former, it means that the 1450234353Sdim // path terminated within a function call. We must then take the 1451234353Sdim // current contents of the active path and place it within 1452234353Sdim // a new PathDiagnosticCallPiece. 1453239462Sdim PathDiagnosticCallPiece *C; 1454239462Sdim if (VisitedEntireCall) { 1455239462Sdim C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); 1456239462Sdim } else { 1457239462Sdim const Decl *Caller = CE->getLocationContext()->getDecl(); 1458234353Sdim C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 1459251662Sdim LCM[&C->path] = CE->getCalleeContext(); 1460234353Sdim } 1461239462Sdim 1462234353Sdim C->setCallee(*CE, SM); 1463239462Sdim EB.addContext(C->getLocation()); 1464234353Sdim 1465234353Sdim if (!CallStack.empty()) { 1466234353Sdim assert(CallStack.back().first == C); 1467234353Sdim CallStack.pop_back(); 1468234353Sdim } 1469234353Sdim break; 1470234353Sdim } 1471234353Sdim 1472234353Sdim // Note that is important that we update the LocationContext 1473234353Sdim // after looking at CallExits. CallExit basically adds an 1474234353Sdim // edge in the *caller*, so we don't want to update the LocationContext 1475234353Sdim // too soon. 1476234353Sdim PDB.LC = N->getLocationContext(); 1477234353Sdim 1478218887Sdim // Block edges. 1479249423Sdim if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) { 1480239462Sdim // Does this represent entering a call? If so, look at propagating 1481239462Sdim // interesting symbols across call boundaries. 1482239462Sdim if (NextNode) { 1483239462Sdim const LocationContext *CallerCtx = NextNode->getLocationContext(); 1484239462Sdim const LocationContext *CalleeCtx = PDB.LC; 1485239462Sdim if (CallerCtx != CalleeCtx) { 1486239462Sdim reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, 1487276479Sdim N->getState().get(), 1488239462Sdim CalleeCtx, CallerCtx); 1489239462Sdim } 1490239462Sdim } 1491239462Sdim 1492218887Sdim // Are we jumping to the head of a loop? Add a special diagnostic. 1493243830Sdim if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { 1494234353Sdim PathDiagnosticLocation L(Loop, SM, PDB.LC); 1495276479Sdim const CompoundStmt *CS = nullptr; 1496218887Sdim 1497243830Sdim if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) 1498243830Sdim CS = dyn_cast<CompoundStmt>(FS->getBody()); 1499243830Sdim else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) 1500243830Sdim CS = dyn_cast<CompoundStmt>(WS->getBody()); 1501218887Sdim 1502218887Sdim PathDiagnosticEventPiece *p = 1503218887Sdim new PathDiagnosticEventPiece(L, 1504218887Sdim "Looping back to the head of the loop"); 1505234353Sdim p->setPrunable(true); 1506218887Sdim 1507218887Sdim EB.addEdge(p->getLocation(), true); 1508234353Sdim PD.getActivePath().push_front(p); 1509218887Sdim 1510218887Sdim if (CS) { 1511226633Sdim PathDiagnosticLocation BL = 1512226633Sdim PathDiagnosticLocation::createEndBrace(CS, SM); 1513218887Sdim EB.addEdge(BL); 1514218887Sdim } 1515218887Sdim } 1516249423Sdim 1517249423Sdim const CFGBlock *BSrc = BE->getSrc(); 1518249423Sdim ParentMap &PM = PDB.getParentMap(); 1519249423Sdim 1520249423Sdim if (const Stmt *Term = BSrc->getTerminator()) { 1521249423Sdim // Are we jumping past the loop body without ever executing the 1522249423Sdim // loop (because the condition was false)? 1523249423Sdim if (isLoopJumpPastBody(Term, &*BE) && 1524249423Sdim !isInLoopBody(PM, 1525249423Sdim getStmtBeforeCond(PM, 1526249423Sdim BSrc->getTerminatorCondition(), 1527249423Sdim N), 1528249423Sdim Term)) { 1529249423Sdim PathDiagnosticLocation L(Term, SM, PDB.LC); 1530249423Sdim PathDiagnosticEventPiece *PE = 1531249423Sdim new PathDiagnosticEventPiece(L, "Loop body executed 0 times"); 1532249423Sdim PE->setPrunable(true); 1533249423Sdim 1534249423Sdim EB.addEdge(PE->getLocation(), true); 1535249423Sdim PD.getActivePath().push_front(PE); 1536249423Sdim } 1537249423Sdim 1538249423Sdim // In any case, add the terminator as the current statement 1539249423Sdim // context for control edges. 1540218887Sdim EB.addContext(Term); 1541249423Sdim } 1542218887Sdim 1543218887Sdim break; 1544218887Sdim } 1545218887Sdim 1546249423Sdim if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) { 1547249423Sdim Optional<CFGElement> First = BE->getFirstElement(); 1548249423Sdim if (Optional<CFGStmt> S = First ? First->getAs<CFGStmt>() : None) { 1549221345Sdim const Stmt *stmt = S->getStmt(); 1550221345Sdim if (IsControlFlowExpr(stmt)) { 1551218887Sdim // Add the proper context for '&&', '||', and '?'. 1552221345Sdim EB.addContext(stmt); 1553218887Sdim } 1554218887Sdim else 1555221345Sdim EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt()); 1556218887Sdim } 1557218887Sdim 1558218887Sdim break; 1559218887Sdim } 1560234353Sdim 1561234353Sdim 1562218887Sdim } while (0); 1563218887Sdim 1564218887Sdim if (!NextNode) 1565218887Sdim continue; 1566218887Sdim 1567226633Sdim // Add pieces from custom visitors. 1568226633Sdim BugReport *R = PDB.getBugReport(); 1569280031Sdim for (auto &V : visitors) { 1570280031Sdim if (PathDiagnosticPiece *p = V->VisitNode(N, NextNode, PDB, *R)) { 1571218887Sdim const PathDiagnosticLocation &Loc = p->getLocation(); 1572218887Sdim EB.addEdge(Loc, true); 1573234353Sdim PD.getActivePath().push_front(p); 1574234353Sdim updateStackPiecesWithMessage(p, CallStack); 1575234353Sdim 1576218887Sdim if (const Stmt *S = Loc.asStmt()) 1577218887Sdim EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 1578218887Sdim } 1579218887Sdim } 1580218887Sdim } 1581243830Sdim 1582243830Sdim return PDB.getBugReport()->isValid(); 1583218887Sdim} 1584218887Sdim 1585251662Sdim/// \brief Adds a sanitized control-flow diagnostic edge to a path. 1586251662Sdimstatic void addEdgeToPath(PathPieces &path, 1587251662Sdim PathDiagnosticLocation &PrevLoc, 1588251662Sdim PathDiagnosticLocation NewLoc, 1589251662Sdim const LocationContext *LC) { 1590251662Sdim if (!NewLoc.isValid()) 1591251662Sdim return; 1592251662Sdim 1593251662Sdim SourceLocation NewLocL = NewLoc.asLocation(); 1594261991Sdim if (NewLocL.isInvalid()) 1595251662Sdim return; 1596251662Sdim 1597261991Sdim if (!PrevLoc.isValid() || !PrevLoc.asLocation().isValid()) { 1598251662Sdim PrevLoc = NewLoc; 1599251662Sdim return; 1600251662Sdim } 1601251662Sdim 1602261991Sdim // Ignore self-edges, which occur when there are multiple nodes at the same 1603261991Sdim // statement. 1604261991Sdim if (NewLoc.asStmt() && NewLoc.asStmt() == PrevLoc.asStmt()) 1605251662Sdim return; 1606251662Sdim 1607251662Sdim path.push_front(new PathDiagnosticControlFlowPiece(NewLoc, 1608251662Sdim PrevLoc)); 1609251662Sdim PrevLoc = NewLoc; 1610251662Sdim} 1611251662Sdim 1612261991Sdim/// A customized wrapper for CFGBlock::getTerminatorCondition() 1613261991Sdim/// which returns the element for ObjCForCollectionStmts. 1614261991Sdimstatic const Stmt *getTerminatorCondition(const CFGBlock *B) { 1615261991Sdim const Stmt *S = B->getTerminatorCondition(); 1616261991Sdim if (const ObjCForCollectionStmt *FS = 1617261991Sdim dyn_cast_or_null<ObjCForCollectionStmt>(S)) 1618261991Sdim return FS->getElement(); 1619261991Sdim return S; 1620261991Sdim} 1621261991Sdim 1622261991Sdimstatic const char StrEnteringLoop[] = "Entering loop body"; 1623261991Sdimstatic const char StrLoopBodyZero[] = "Loop body executed 0 times"; 1624261991Sdimstatic const char StrLoopRangeEmpty[] = 1625261991Sdim "Loop body skipped when range is empty"; 1626261991Sdimstatic const char StrLoopCollectionEmpty[] = 1627261991Sdim "Loop body skipped when collection is empty"; 1628261991Sdim 1629280031Sdimstatic bool GenerateAlternateExtensivePathDiagnostic( 1630280031Sdim PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, 1631280031Sdim LocationContextMap &LCM, 1632280031Sdim ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors) { 1633251662Sdim 1634251662Sdim BugReport *report = PDB.getBugReport(); 1635251662Sdim const SourceManager& SM = PDB.getSourceManager(); 1636251662Sdim StackDiagVector CallStack; 1637251662Sdim InterestingExprs IE; 1638251662Sdim 1639261991Sdim PathDiagnosticLocation PrevLoc = PD.getLocation(); 1640251662Sdim 1641251662Sdim const ExplodedNode *NextNode = N->getFirstPred(); 1642251662Sdim while (NextNode) { 1643251662Sdim N = NextNode; 1644251662Sdim NextNode = N->getFirstPred(); 1645251662Sdim ProgramPoint P = N->getLocation(); 1646251662Sdim 1647251662Sdim do { 1648261991Sdim // Have we encountered an entrance to a call? It may be 1649261991Sdim // the case that we have not encountered a matching 1650261991Sdim // call exit before this point. This means that the path 1651261991Sdim // terminated within the call itself. 1652261991Sdim if (Optional<CallEnter> CE = P.getAs<CallEnter>()) { 1653261991Sdim // Add an edge to the start of the function. 1654261991Sdim const StackFrameContext *CalleeLC = CE->getCalleeContext(); 1655261991Sdim const Decl *D = CalleeLC->getDecl(); 1656261991Sdim addEdgeToPath(PD.getActivePath(), PrevLoc, 1657261991Sdim PathDiagnosticLocation::createBegin(D, SM), 1658261991Sdim CalleeLC); 1659251662Sdim 1660261991Sdim // Did we visit an entire call? 1661261991Sdim bool VisitedEntireCall = PD.isWithinCall(); 1662261991Sdim PD.popActivePath(); 1663261991Sdim 1664261991Sdim PathDiagnosticCallPiece *C; 1665261991Sdim if (VisitedEntireCall) { 1666276479Sdim PathDiagnosticPiece *P = PD.getActivePath().front().get(); 1667261991Sdim C = cast<PathDiagnosticCallPiece>(P); 1668261991Sdim } else { 1669261991Sdim const Decl *Caller = CE->getLocationContext()->getDecl(); 1670261991Sdim C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 1671261991Sdim 1672261991Sdim // Since we just transferred the path over to the call piece, 1673261991Sdim // reset the mapping from active to location context. 1674261991Sdim assert(PD.getActivePath().size() == 1 && 1675261991Sdim PD.getActivePath().front() == C); 1676276479Sdim LCM[&PD.getActivePath()] = nullptr; 1677261991Sdim 1678261991Sdim // Record the location context mapping for the path within 1679261991Sdim // the call. 1680276479Sdim assert(LCM[&C->path] == nullptr || 1681261991Sdim LCM[&C->path] == CE->getCalleeContext()); 1682261991Sdim LCM[&C->path] = CE->getCalleeContext(); 1683261991Sdim 1684261991Sdim // If this is the first item in the active path, record 1685261991Sdim // the new mapping from active path to location context. 1686261991Sdim const LocationContext *&NewLC = LCM[&PD.getActivePath()]; 1687261991Sdim if (!NewLC) 1688261991Sdim NewLC = N->getLocationContext(); 1689261991Sdim 1690261991Sdim PDB.LC = NewLC; 1691261991Sdim } 1692261991Sdim C->setCallee(*CE, SM); 1693261991Sdim 1694261991Sdim // Update the previous location in the active path. 1695261991Sdim PrevLoc = C->getLocation(); 1696261991Sdim 1697261991Sdim if (!CallStack.empty()) { 1698261991Sdim assert(CallStack.back().first == C); 1699261991Sdim CallStack.pop_back(); 1700261991Sdim } 1701251662Sdim break; 1702251662Sdim } 1703251662Sdim 1704261991Sdim // Query the location context here and the previous location 1705261991Sdim // as processing CallEnter may change the active path. 1706261991Sdim PDB.LC = N->getLocationContext(); 1707261991Sdim 1708261991Sdim // Record the mapping from the active path to the location 1709261991Sdim // context. 1710261991Sdim assert(!LCM[&PD.getActivePath()] || 1711261991Sdim LCM[&PD.getActivePath()] == PDB.LC); 1712261991Sdim LCM[&PD.getActivePath()] = PDB.LC; 1713261991Sdim 1714251662Sdim // Have we encountered an exit from a function call? 1715251662Sdim if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) { 1716251662Sdim const Stmt *S = CE->getCalleeContext()->getCallSite(); 1717251662Sdim // Propagate the interesting symbols accordingly. 1718251662Sdim if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) { 1719251662Sdim reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1720276479Sdim N->getState().get(), Ex, 1721251662Sdim N->getLocationContext()); 1722251662Sdim } 1723251662Sdim 1724251662Sdim // We are descending into a call (backwards). Construct 1725251662Sdim // a new call piece to contain the path pieces for that call. 1726251662Sdim PathDiagnosticCallPiece *C = 1727251662Sdim PathDiagnosticCallPiece::construct(N, *CE, SM); 1728251662Sdim 1729251662Sdim // Record the location context for this call piece. 1730251662Sdim LCM[&C->path] = CE->getCalleeContext(); 1731251662Sdim 1732251662Sdim // Add the edge to the return site. 1733261991Sdim addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, PDB.LC); 1734261991Sdim PD.getActivePath().push_front(C); 1735261991Sdim PrevLoc.invalidate(); 1736251662Sdim 1737251662Sdim // Make the contents of the call the active path for now. 1738251662Sdim PD.pushActivePath(&C->path); 1739251662Sdim CallStack.push_back(StackDiagPair(C, N)); 1740251662Sdim break; 1741251662Sdim } 1742251662Sdim 1743261991Sdim if (Optional<PostStmt> PS = P.getAs<PostStmt>()) { 1744261991Sdim // For expressions, make sure we propagate the 1745261991Sdim // interesting symbols correctly. 1746261991Sdim if (const Expr *Ex = PS->getStmtAs<Expr>()) 1747261991Sdim reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 1748276479Sdim N->getState().get(), Ex, 1749261991Sdim N->getLocationContext()); 1750251662Sdim 1751261991Sdim // Add an edge. If this is an ObjCForCollectionStmt do 1752261991Sdim // not add an edge here as it appears in the CFG both 1753261991Sdim // as a terminator and as a terminator condition. 1754261991Sdim if (!isa<ObjCForCollectionStmt>(PS->getStmt())) { 1755261991Sdim PathDiagnosticLocation L = 1756261991Sdim PathDiagnosticLocation(PS->getStmt(), SM, PDB.LC); 1757261991Sdim addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); 1758251662Sdim } 1759251662Sdim break; 1760251662Sdim } 1761251662Sdim 1762251662Sdim // Block edges. 1763251662Sdim if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) { 1764251662Sdim // Does this represent entering a call? If so, look at propagating 1765251662Sdim // interesting symbols across call boundaries. 1766251662Sdim if (NextNode) { 1767251662Sdim const LocationContext *CallerCtx = NextNode->getLocationContext(); 1768251662Sdim const LocationContext *CalleeCtx = PDB.LC; 1769251662Sdim if (CallerCtx != CalleeCtx) { 1770251662Sdim reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, 1771276479Sdim N->getState().get(), 1772251662Sdim CalleeCtx, CallerCtx); 1773251662Sdim } 1774251662Sdim } 1775251662Sdim 1776251662Sdim // Are we jumping to the head of a loop? Add a special diagnostic. 1777251662Sdim if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { 1778251662Sdim PathDiagnosticLocation L(Loop, SM, PDB.LC); 1779276479Sdim const Stmt *Body = nullptr; 1780251662Sdim 1781251662Sdim if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) 1782261991Sdim Body = FS->getBody(); 1783251662Sdim else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) 1784261991Sdim Body = WS->getBody(); 1785261991Sdim else if (const ObjCForCollectionStmt *OFS = 1786261991Sdim dyn_cast<ObjCForCollectionStmt>(Loop)) { 1787261991Sdim Body = OFS->getBody(); 1788261991Sdim } else if (const CXXForRangeStmt *FRS = 1789261991Sdim dyn_cast<CXXForRangeStmt>(Loop)) { 1790261991Sdim Body = FRS->getBody(); 1791261991Sdim } 1792261991Sdim // do-while statements are explicitly excluded here 1793251662Sdim 1794251662Sdim PathDiagnosticEventPiece *p = 1795251662Sdim new PathDiagnosticEventPiece(L, "Looping back to the head " 1796251662Sdim "of the loop"); 1797251662Sdim p->setPrunable(true); 1798251662Sdim 1799261991Sdim addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC); 1800251662Sdim PD.getActivePath().push_front(p); 1801251662Sdim 1802261991Sdim if (const CompoundStmt *CS = dyn_cast_or_null<CompoundStmt>(Body)) { 1803251662Sdim addEdgeToPath(PD.getActivePath(), PrevLoc, 1804261991Sdim PathDiagnosticLocation::createEndBrace(CS, SM), 1805261991Sdim PDB.LC); 1806251662Sdim } 1807251662Sdim } 1808261991Sdim 1809251662Sdim const CFGBlock *BSrc = BE->getSrc(); 1810251662Sdim ParentMap &PM = PDB.getParentMap(); 1811251662Sdim 1812251662Sdim if (const Stmt *Term = BSrc->getTerminator()) { 1813251662Sdim // Are we jumping past the loop body without ever executing the 1814251662Sdim // loop (because the condition was false)? 1815261991Sdim if (isLoop(Term)) { 1816261991Sdim const Stmt *TermCond = getTerminatorCondition(BSrc); 1817261991Sdim bool IsInLoopBody = 1818261991Sdim isInLoopBody(PM, getStmtBeforeCond(PM, TermCond, N), Term); 1819261991Sdim 1820276479Sdim const char *str = nullptr; 1821261991Sdim 1822261991Sdim if (isJumpToFalseBranch(&*BE)) { 1823261991Sdim if (!IsInLoopBody) { 1824261991Sdim if (isa<ObjCForCollectionStmt>(Term)) { 1825261991Sdim str = StrLoopCollectionEmpty; 1826261991Sdim } else if (isa<CXXForRangeStmt>(Term)) { 1827261991Sdim str = StrLoopRangeEmpty; 1828261991Sdim } else { 1829261991Sdim str = StrLoopBodyZero; 1830261991Sdim } 1831261991Sdim } 1832261991Sdim } else { 1833261991Sdim str = StrEnteringLoop; 1834261991Sdim } 1835261991Sdim 1836261991Sdim if (str) { 1837261991Sdim PathDiagnosticLocation L(TermCond ? TermCond : Term, SM, PDB.LC); 1838261991Sdim PathDiagnosticEventPiece *PE = 1839261991Sdim new PathDiagnosticEventPiece(L, str); 1840261991Sdim PE->setPrunable(true); 1841261991Sdim addEdgeToPath(PD.getActivePath(), PrevLoc, 1842261991Sdim PE->getLocation(), PDB.LC); 1843261991Sdim PD.getActivePath().push_front(PE); 1844261991Sdim } 1845261991Sdim } else if (isa<BreakStmt>(Term) || isa<ContinueStmt>(Term) || 1846261991Sdim isa<GotoStmt>(Term)) { 1847251662Sdim PathDiagnosticLocation L(Term, SM, PDB.LC); 1848261991Sdim addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); 1849251662Sdim } 1850251662Sdim } 1851251662Sdim break; 1852251662Sdim } 1853251662Sdim } while (0); 1854251662Sdim 1855251662Sdim if (!NextNode) 1856251662Sdim continue; 1857251662Sdim 1858251662Sdim // Add pieces from custom visitors. 1859280031Sdim for (auto &V : visitors) { 1860280031Sdim if (PathDiagnosticPiece *p = V->VisitNode(N, NextNode, PDB, *report)) { 1861261991Sdim addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC); 1862251662Sdim PD.getActivePath().push_front(p); 1863251662Sdim updateStackPiecesWithMessage(p, CallStack); 1864251662Sdim } 1865251662Sdim } 1866251662Sdim } 1867251662Sdim 1868261991Sdim // Add an edge to the start of the function. 1869261991Sdim // We'll prune it out later, but it helps make diagnostics more uniform. 1870261991Sdim const StackFrameContext *CalleeLC = PDB.LC->getCurrentStackFrame(); 1871261991Sdim const Decl *D = CalleeLC->getDecl(); 1872261991Sdim addEdgeToPath(PD.getActivePath(), PrevLoc, 1873261991Sdim PathDiagnosticLocation::createBegin(D, SM), 1874261991Sdim CalleeLC); 1875261991Sdim 1876251662Sdim return report->isValid(); 1877251662Sdim} 1878251662Sdim 1879261991Sdimstatic const Stmt *getLocStmt(PathDiagnosticLocation L) { 1880251662Sdim if (!L.isValid()) 1881276479Sdim return nullptr; 1882251662Sdim return L.asStmt(); 1883251662Sdim} 1884251662Sdim 1885261991Sdimstatic const Stmt *getStmtParent(const Stmt *S, const ParentMap &PM) { 1886251662Sdim if (!S) 1887276479Sdim return nullptr; 1888261991Sdim 1889261991Sdim while (true) { 1890261991Sdim S = PM.getParentIgnoreParens(S); 1891261991Sdim 1892261991Sdim if (!S) 1893261991Sdim break; 1894261991Sdim 1895261991Sdim if (isa<ExprWithCleanups>(S) || 1896261991Sdim isa<CXXBindTemporaryExpr>(S) || 1897261991Sdim isa<SubstNonTypeTemplateParmExpr>(S)) 1898261991Sdim continue; 1899261991Sdim 1900261991Sdim break; 1901261991Sdim } 1902261991Sdim 1903261991Sdim return S; 1904251662Sdim} 1905251662Sdim 1906251662Sdimstatic bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) { 1907251662Sdim switch (S->getStmtClass()) { 1908261991Sdim case Stmt::BinaryOperatorClass: { 1909261991Sdim const BinaryOperator *BO = cast<BinaryOperator>(S); 1910261991Sdim if (!BO->isLogicalOp()) 1911261991Sdim return false; 1912261991Sdim return BO->getLHS() == Cond || BO->getRHS() == Cond; 1913261991Sdim } 1914261991Sdim case Stmt::IfStmtClass: 1915261991Sdim return cast<IfStmt>(S)->getCond() == Cond; 1916251662Sdim case Stmt::ForStmtClass: 1917251662Sdim return cast<ForStmt>(S)->getCond() == Cond; 1918251662Sdim case Stmt::WhileStmtClass: 1919251662Sdim return cast<WhileStmt>(S)->getCond() == Cond; 1920251662Sdim case Stmt::DoStmtClass: 1921251662Sdim return cast<DoStmt>(S)->getCond() == Cond; 1922251662Sdim case Stmt::ChooseExprClass: 1923251662Sdim return cast<ChooseExpr>(S)->getCond() == Cond; 1924251662Sdim case Stmt::IndirectGotoStmtClass: 1925251662Sdim return cast<IndirectGotoStmt>(S)->getTarget() == Cond; 1926251662Sdim case Stmt::SwitchStmtClass: 1927251662Sdim return cast<SwitchStmt>(S)->getCond() == Cond; 1928251662Sdim case Stmt::BinaryConditionalOperatorClass: 1929251662Sdim return cast<BinaryConditionalOperator>(S)->getCond() == Cond; 1930261991Sdim case Stmt::ConditionalOperatorClass: { 1931261991Sdim const ConditionalOperator *CO = cast<ConditionalOperator>(S); 1932261991Sdim return CO->getCond() == Cond || 1933261991Sdim CO->getLHS() == Cond || 1934261991Sdim CO->getRHS() == Cond; 1935261991Sdim } 1936251662Sdim case Stmt::ObjCForCollectionStmtClass: 1937251662Sdim return cast<ObjCForCollectionStmt>(S)->getElement() == Cond; 1938261991Sdim case Stmt::CXXForRangeStmtClass: { 1939261991Sdim const CXXForRangeStmt *FRS = cast<CXXForRangeStmt>(S); 1940261991Sdim return FRS->getCond() == Cond || FRS->getRangeInit() == Cond; 1941261991Sdim } 1942251662Sdim default: 1943251662Sdim return false; 1944251662Sdim } 1945251662Sdim} 1946251662Sdim 1947261991Sdimstatic bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL) { 1948261991Sdim if (const ForStmt *FS = dyn_cast<ForStmt>(FL)) 1949261991Sdim return FS->getInc() == S || FS->getInit() == S; 1950261991Sdim if (const CXXForRangeStmt *FRS = dyn_cast<CXXForRangeStmt>(FL)) 1951261991Sdim return FRS->getInc() == S || FRS->getRangeStmt() == S || 1952261991Sdim FRS->getLoopVarStmt() || FRS->getRangeInit() == S; 1953261991Sdim return false; 1954261991Sdim} 1955251662Sdim 1956251662Sdimtypedef llvm::DenseSet<const PathDiagnosticCallPiece *> 1957251662Sdim OptimizedCallsSet; 1958251662Sdim 1959261991Sdim/// Adds synthetic edges from top-level statements to their subexpressions. 1960261991Sdim/// 1961261991Sdim/// This avoids a "swoosh" effect, where an edge from a top-level statement A 1962261991Sdim/// points to a sub-expression B.1 that's not at the start of B. In these cases, 1963261991Sdim/// we'd like to see an edge from A to B, then another one from B to B.1. 1964261991Sdimstatic void addContextEdges(PathPieces &pieces, SourceManager &SM, 1965261991Sdim const ParentMap &PM, const LocationContext *LCtx) { 1966261991Sdim PathPieces::iterator Prev = pieces.end(); 1967261991Sdim for (PathPieces::iterator I = pieces.begin(), E = Prev; I != E; 1968261991Sdim Prev = I, ++I) { 1969261991Sdim PathDiagnosticControlFlowPiece *Piece = 1970261991Sdim dyn_cast<PathDiagnosticControlFlowPiece>(*I); 1971261991Sdim 1972261991Sdim if (!Piece) 1973261991Sdim continue; 1974261991Sdim 1975261991Sdim PathDiagnosticLocation SrcLoc = Piece->getStartLocation(); 1976261991Sdim SmallVector<PathDiagnosticLocation, 4> SrcContexts; 1977261991Sdim 1978261991Sdim PathDiagnosticLocation NextSrcContext = SrcLoc; 1979276479Sdim const Stmt *InnerStmt = nullptr; 1980261991Sdim while (NextSrcContext.isValid() && NextSrcContext.asStmt() != InnerStmt) { 1981261991Sdim SrcContexts.push_back(NextSrcContext); 1982261991Sdim InnerStmt = NextSrcContext.asStmt(); 1983261991Sdim NextSrcContext = getEnclosingStmtLocation(InnerStmt, SM, PM, LCtx, 1984261991Sdim /*allowNested=*/true); 1985261991Sdim } 1986261991Sdim 1987261991Sdim // Repeatedly split the edge as necessary. 1988261991Sdim // This is important for nested logical expressions (||, &&, ?:) where we 1989261991Sdim // want to show all the levels of context. 1990261991Sdim while (true) { 1991261991Sdim const Stmt *Dst = getLocStmt(Piece->getEndLocation()); 1992261991Sdim 1993261991Sdim // We are looking at an edge. Is the destination within a larger 1994261991Sdim // expression? 1995261991Sdim PathDiagnosticLocation DstContext = 1996261991Sdim getEnclosingStmtLocation(Dst, SM, PM, LCtx, /*allowNested=*/true); 1997261991Sdim if (!DstContext.isValid() || DstContext.asStmt() == Dst) 1998261991Sdim break; 1999261991Sdim 2000261991Sdim // If the source is in the same context, we're already good. 2001261991Sdim if (std::find(SrcContexts.begin(), SrcContexts.end(), DstContext) != 2002261991Sdim SrcContexts.end()) 2003261991Sdim break; 2004261991Sdim 2005261991Sdim // Update the subexpression node to point to the context edge. 2006261991Sdim Piece->setStartLocation(DstContext); 2007261991Sdim 2008261991Sdim // Try to extend the previous edge if it's at the same level as the source 2009261991Sdim // context. 2010261991Sdim if (Prev != E) { 2011261991Sdim PathDiagnosticControlFlowPiece *PrevPiece = 2012261991Sdim dyn_cast<PathDiagnosticControlFlowPiece>(*Prev); 2013261991Sdim 2014261991Sdim if (PrevPiece) { 2015261991Sdim if (const Stmt *PrevSrc = getLocStmt(PrevPiece->getStartLocation())) { 2016261991Sdim const Stmt *PrevSrcParent = getStmtParent(PrevSrc, PM); 2017261991Sdim if (PrevSrcParent == getStmtParent(getLocStmt(DstContext), PM)) { 2018261991Sdim PrevPiece->setEndLocation(DstContext); 2019261991Sdim break; 2020261991Sdim } 2021261991Sdim } 2022261991Sdim } 2023261991Sdim } 2024261991Sdim 2025261991Sdim // Otherwise, split the current edge into a context edge and a 2026261991Sdim // subexpression edge. Note that the context statement may itself have 2027261991Sdim // context. 2028261991Sdim Piece = new PathDiagnosticControlFlowPiece(SrcLoc, DstContext); 2029261991Sdim I = pieces.insert(I, Piece); 2030261991Sdim } 2031261991Sdim } 2032251662Sdim} 2033251662Sdim 2034261991Sdim/// \brief Move edges from a branch condition to a branch target 2035261991Sdim/// when the condition is simple. 2036261991Sdim/// 2037261991Sdim/// This restructures some of the work of addContextEdges. That function 2038261991Sdim/// creates edges this may destroy, but they work together to create a more 2039261991Sdim/// aesthetically set of edges around branches. After the call to 2040261991Sdim/// addContextEdges, we may have (1) an edge to the branch, (2) an edge from 2041261991Sdim/// the branch to the branch condition, and (3) an edge from the branch 2042261991Sdim/// condition to the branch target. We keep (1), but may wish to remove (2) 2043261991Sdim/// and move the source of (3) to the branch if the branch condition is simple. 2044261991Sdim/// 2045261991Sdimstatic void simplifySimpleBranches(PathPieces &pieces) { 2046261991Sdim for (PathPieces::iterator I = pieces.begin(), E = pieces.end(); I != E; ++I) { 2047261991Sdim 2048261991Sdim PathDiagnosticControlFlowPiece *PieceI = 2049261991Sdim dyn_cast<PathDiagnosticControlFlowPiece>(*I); 2050261991Sdim 2051261991Sdim if (!PieceI) 2052261991Sdim continue; 2053261991Sdim 2054261991Sdim const Stmt *s1Start = getLocStmt(PieceI->getStartLocation()); 2055261991Sdim const Stmt *s1End = getLocStmt(PieceI->getEndLocation()); 2056261991Sdim 2057261991Sdim if (!s1Start || !s1End) 2058261991Sdim continue; 2059261991Sdim 2060261991Sdim PathPieces::iterator NextI = I; ++NextI; 2061261991Sdim if (NextI == E) 2062261991Sdim break; 2063261991Sdim 2064276479Sdim PathDiagnosticControlFlowPiece *PieceNextI = nullptr; 2065261991Sdim 2066261991Sdim while (true) { 2067261991Sdim if (NextI == E) 2068261991Sdim break; 2069261991Sdim 2070261991Sdim PathDiagnosticEventPiece *EV = dyn_cast<PathDiagnosticEventPiece>(*NextI); 2071261991Sdim if (EV) { 2072261991Sdim StringRef S = EV->getString(); 2073261991Sdim if (S == StrEnteringLoop || S == StrLoopBodyZero || 2074261991Sdim S == StrLoopCollectionEmpty || S == StrLoopRangeEmpty) { 2075261991Sdim ++NextI; 2076261991Sdim continue; 2077261991Sdim } 2078261991Sdim break; 2079261991Sdim } 2080261991Sdim 2081261991Sdim PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); 2082261991Sdim break; 2083261991Sdim } 2084261991Sdim 2085261991Sdim if (!PieceNextI) 2086261991Sdim continue; 2087261991Sdim 2088261991Sdim const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation()); 2089261991Sdim const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation()); 2090261991Sdim 2091261991Sdim if (!s2Start || !s2End || s1End != s2Start) 2092261991Sdim continue; 2093261991Sdim 2094261991Sdim // We only perform this transformation for specific branch kinds. 2095261991Sdim // We don't want to do this for do..while, for example. 2096261991Sdim if (!(isa<ForStmt>(s1Start) || isa<WhileStmt>(s1Start) || 2097261991Sdim isa<IfStmt>(s1Start) || isa<ObjCForCollectionStmt>(s1Start) || 2098261991Sdim isa<CXXForRangeStmt>(s1Start))) 2099261991Sdim continue; 2100261991Sdim 2101261991Sdim // Is s1End the branch condition? 2102261991Sdim if (!isConditionForTerminator(s1Start, s1End)) 2103261991Sdim continue; 2104261991Sdim 2105261991Sdim // Perform the hoisting by eliminating (2) and changing the start 2106261991Sdim // location of (3). 2107261991Sdim PieceNextI->setStartLocation(PieceI->getStartLocation()); 2108261991Sdim I = pieces.erase(I); 2109261991Sdim } 2110261991Sdim} 2111261991Sdim 2112261991Sdim/// Returns the number of bytes in the given (character-based) SourceRange. 2113261991Sdim/// 2114261991Sdim/// If the locations in the range are not on the same line, returns None. 2115261991Sdim/// 2116261991Sdim/// Note that this does not do a precise user-visible character or column count. 2117261991Sdimstatic Optional<size_t> getLengthOnSingleLine(SourceManager &SM, 2118261991Sdim SourceRange Range) { 2119261991Sdim SourceRange ExpansionRange(SM.getExpansionLoc(Range.getBegin()), 2120261991Sdim SM.getExpansionRange(Range.getEnd()).second); 2121261991Sdim 2122261991Sdim FileID FID = SM.getFileID(ExpansionRange.getBegin()); 2123261991Sdim if (FID != SM.getFileID(ExpansionRange.getEnd())) 2124261991Sdim return None; 2125261991Sdim 2126261991Sdim bool Invalid; 2127261991Sdim const llvm::MemoryBuffer *Buffer = SM.getBuffer(FID, &Invalid); 2128261991Sdim if (Invalid) 2129261991Sdim return None; 2130261991Sdim 2131261991Sdim unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin()); 2132261991Sdim unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd()); 2133261991Sdim StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset); 2134261991Sdim 2135261991Sdim // We're searching the raw bytes of the buffer here, which might include 2136261991Sdim // escaped newlines and such. That's okay; we're trying to decide whether the 2137261991Sdim // SourceRange is covering a large or small amount of space in the user's 2138261991Sdim // editor. 2139261991Sdim if (Snippet.find_first_of("\r\n") != StringRef::npos) 2140261991Sdim return None; 2141261991Sdim 2142261991Sdim // This isn't Unicode-aware, but it doesn't need to be. 2143261991Sdim return Snippet.size(); 2144261991Sdim} 2145261991Sdim 2146261991Sdim/// \sa getLengthOnSingleLine(SourceManager, SourceRange) 2147261991Sdimstatic Optional<size_t> getLengthOnSingleLine(SourceManager &SM, 2148261991Sdim const Stmt *S) { 2149261991Sdim return getLengthOnSingleLine(SM, S->getSourceRange()); 2150261991Sdim} 2151261991Sdim 2152261991Sdim/// Eliminate two-edge cycles created by addContextEdges(). 2153261991Sdim/// 2154261991Sdim/// Once all the context edges are in place, there are plenty of cases where 2155261991Sdim/// there's a single edge from a top-level statement to a subexpression, 2156261991Sdim/// followed by a single path note, and then a reverse edge to get back out to 2157261991Sdim/// the top level. If the statement is simple enough, the subexpression edges 2158261991Sdim/// just add noise and make it harder to understand what's going on. 2159261991Sdim/// 2160261991Sdim/// This function only removes edges in pairs, because removing only one edge 2161261991Sdim/// might leave other edges dangling. 2162261991Sdim/// 2163261991Sdim/// This will not remove edges in more complicated situations: 2164261991Sdim/// - if there is more than one "hop" leading to or from a subexpression. 2165261991Sdim/// - if there is an inlined call between the edges instead of a single event. 2166261991Sdim/// - if the whole statement is large enough that having subexpression arrows 2167261991Sdim/// might be helpful. 2168261991Sdimstatic void removeContextCycles(PathPieces &Path, SourceManager &SM, 2169261991Sdim ParentMap &PM) { 2170261991Sdim for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) { 2171261991Sdim // Pattern match the current piece and its successor. 2172261991Sdim PathDiagnosticControlFlowPiece *PieceI = 2173261991Sdim dyn_cast<PathDiagnosticControlFlowPiece>(*I); 2174261991Sdim 2175261991Sdim if (!PieceI) { 2176261991Sdim ++I; 2177261991Sdim continue; 2178261991Sdim } 2179261991Sdim 2180261991Sdim const Stmt *s1Start = getLocStmt(PieceI->getStartLocation()); 2181261991Sdim const Stmt *s1End = getLocStmt(PieceI->getEndLocation()); 2182261991Sdim 2183261991Sdim PathPieces::iterator NextI = I; ++NextI; 2184261991Sdim if (NextI == E) 2185261991Sdim break; 2186261991Sdim 2187261991Sdim PathDiagnosticControlFlowPiece *PieceNextI = 2188261991Sdim dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); 2189261991Sdim 2190261991Sdim if (!PieceNextI) { 2191261991Sdim if (isa<PathDiagnosticEventPiece>(*NextI)) { 2192261991Sdim ++NextI; 2193261991Sdim if (NextI == E) 2194261991Sdim break; 2195261991Sdim PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); 2196261991Sdim } 2197261991Sdim 2198261991Sdim if (!PieceNextI) { 2199261991Sdim ++I; 2200261991Sdim continue; 2201261991Sdim } 2202261991Sdim } 2203261991Sdim 2204261991Sdim const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation()); 2205261991Sdim const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation()); 2206261991Sdim 2207261991Sdim if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) { 2208261991Sdim const size_t MAX_SHORT_LINE_LENGTH = 80; 2209261991Sdim Optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start); 2210261991Sdim if (s1Length && *s1Length <= MAX_SHORT_LINE_LENGTH) { 2211261991Sdim Optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start); 2212261991Sdim if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) { 2213261991Sdim Path.erase(I); 2214261991Sdim I = Path.erase(NextI); 2215261991Sdim continue; 2216261991Sdim } 2217261991Sdim } 2218261991Sdim } 2219261991Sdim 2220261991Sdim ++I; 2221261991Sdim } 2222261991Sdim} 2223261991Sdim 2224261991Sdim/// \brief Return true if X is contained by Y. 2225261991Sdimstatic bool lexicalContains(ParentMap &PM, 2226261991Sdim const Stmt *X, 2227261991Sdim const Stmt *Y) { 2228261991Sdim while (X) { 2229261991Sdim if (X == Y) 2230261991Sdim return true; 2231261991Sdim X = PM.getParent(X); 2232261991Sdim } 2233261991Sdim return false; 2234261991Sdim} 2235261991Sdim 2236261991Sdim// Remove short edges on the same line less than 3 columns in difference. 2237261991Sdimstatic void removePunyEdges(PathPieces &path, 2238261991Sdim SourceManager &SM, 2239261991Sdim ParentMap &PM) { 2240261991Sdim 2241261991Sdim bool erased = false; 2242261991Sdim 2243261991Sdim for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; 2244261991Sdim erased ? I : ++I) { 2245261991Sdim 2246261991Sdim erased = false; 2247261991Sdim 2248261991Sdim PathDiagnosticControlFlowPiece *PieceI = 2249261991Sdim dyn_cast<PathDiagnosticControlFlowPiece>(*I); 2250261991Sdim 2251261991Sdim if (!PieceI) 2252261991Sdim continue; 2253261991Sdim 2254261991Sdim const Stmt *start = getLocStmt(PieceI->getStartLocation()); 2255261991Sdim const Stmt *end = getLocStmt(PieceI->getEndLocation()); 2256261991Sdim 2257261991Sdim if (!start || !end) 2258261991Sdim continue; 2259261991Sdim 2260261991Sdim const Stmt *endParent = PM.getParent(end); 2261261991Sdim if (!endParent) 2262261991Sdim continue; 2263261991Sdim 2264261991Sdim if (isConditionForTerminator(end, endParent)) 2265261991Sdim continue; 2266261991Sdim 2267261991Sdim SourceLocation FirstLoc = start->getLocStart(); 2268261991Sdim SourceLocation SecondLoc = end->getLocStart(); 2269261991Sdim 2270261991Sdim if (!SM.isWrittenInSameFile(FirstLoc, SecondLoc)) 2271261991Sdim continue; 2272261991Sdim if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc)) 2273261991Sdim std::swap(SecondLoc, FirstLoc); 2274261991Sdim 2275261991Sdim SourceRange EdgeRange(FirstLoc, SecondLoc); 2276261991Sdim Optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange); 2277261991Sdim 2278261991Sdim // If the statements are on different lines, continue. 2279261991Sdim if (!ByteWidth) 2280261991Sdim continue; 2281261991Sdim 2282261991Sdim const size_t MAX_PUNY_EDGE_LENGTH = 2; 2283261991Sdim if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) { 2284261991Sdim // FIXME: There are enough /bytes/ between the endpoints of the edge, but 2285261991Sdim // there might not be enough /columns/. A proper user-visible column count 2286261991Sdim // is probably too expensive, though. 2287261991Sdim I = path.erase(I); 2288261991Sdim erased = true; 2289261991Sdim continue; 2290261991Sdim } 2291261991Sdim } 2292261991Sdim} 2293261991Sdim 2294261991Sdimstatic void removeIdenticalEvents(PathPieces &path) { 2295261991Sdim for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) { 2296261991Sdim PathDiagnosticEventPiece *PieceI = 2297261991Sdim dyn_cast<PathDiagnosticEventPiece>(*I); 2298261991Sdim 2299261991Sdim if (!PieceI) 2300261991Sdim continue; 2301261991Sdim 2302261991Sdim PathPieces::iterator NextI = I; ++NextI; 2303261991Sdim if (NextI == E) 2304261991Sdim return; 2305261991Sdim 2306261991Sdim PathDiagnosticEventPiece *PieceNextI = 2307261991Sdim dyn_cast<PathDiagnosticEventPiece>(*NextI); 2308261991Sdim 2309261991Sdim if (!PieceNextI) 2310261991Sdim continue; 2311261991Sdim 2312261991Sdim // Erase the second piece if it has the same exact message text. 2313261991Sdim if (PieceI->getString() == PieceNextI->getString()) { 2314261991Sdim path.erase(NextI); 2315261991Sdim } 2316261991Sdim } 2317261991Sdim} 2318261991Sdim 2319251662Sdimstatic bool optimizeEdges(PathPieces &path, SourceManager &SM, 2320251662Sdim OptimizedCallsSet &OCS, 2321251662Sdim LocationContextMap &LCM) { 2322251662Sdim bool hasChanges = false; 2323251662Sdim const LocationContext *LC = LCM[&path]; 2324251662Sdim assert(LC); 2325261991Sdim ParentMap &PM = LC->getParentMap(); 2326251662Sdim 2327251662Sdim for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) { 2328251662Sdim // Optimize subpaths. 2329251662Sdim if (PathDiagnosticCallPiece *CallI = dyn_cast<PathDiagnosticCallPiece>(*I)){ 2330251662Sdim // Record the fact that a call has been optimized so we only do the 2331251662Sdim // effort once. 2332251662Sdim if (!OCS.count(CallI)) { 2333261991Sdim while (optimizeEdges(CallI->path, SM, OCS, LCM)) {} 2334251662Sdim OCS.insert(CallI); 2335251662Sdim } 2336251662Sdim ++I; 2337251662Sdim continue; 2338251662Sdim } 2339251662Sdim 2340251662Sdim // Pattern match the current piece and its successor. 2341251662Sdim PathDiagnosticControlFlowPiece *PieceI = 2342251662Sdim dyn_cast<PathDiagnosticControlFlowPiece>(*I); 2343251662Sdim 2344251662Sdim if (!PieceI) { 2345251662Sdim ++I; 2346251662Sdim continue; 2347251662Sdim } 2348251662Sdim 2349251662Sdim const Stmt *s1Start = getLocStmt(PieceI->getStartLocation()); 2350251662Sdim const Stmt *s1End = getLocStmt(PieceI->getEndLocation()); 2351251662Sdim const Stmt *level1 = getStmtParent(s1Start, PM); 2352251662Sdim const Stmt *level2 = getStmtParent(s1End, PM); 2353251662Sdim 2354251662Sdim PathPieces::iterator NextI = I; ++NextI; 2355251662Sdim if (NextI == E) 2356251662Sdim break; 2357251662Sdim 2358251662Sdim PathDiagnosticControlFlowPiece *PieceNextI = 2359251662Sdim dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); 2360251662Sdim 2361251662Sdim if (!PieceNextI) { 2362251662Sdim ++I; 2363251662Sdim continue; 2364251662Sdim } 2365251662Sdim 2366251662Sdim const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation()); 2367251662Sdim const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation()); 2368251662Sdim const Stmt *level3 = getStmtParent(s2Start, PM); 2369251662Sdim const Stmt *level4 = getStmtParent(s2End, PM); 2370251662Sdim 2371251662Sdim // Rule I. 2372251662Sdim // 2373251662Sdim // If we have two consecutive control edges whose end/begin locations 2374251662Sdim // are at the same level (e.g. statements or top-level expressions within 2375251662Sdim // a compound statement, or siblings share a single ancestor expression), 2376251662Sdim // then merge them if they have no interesting intermediate event. 2377251662Sdim // 2378251662Sdim // For example: 2379251662Sdim // 2380251662Sdim // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common 2381251662Sdim // parent is '1'. Here 'x.y.z' represents the hierarchy of statements. 2382251662Sdim // 2383251662Sdim // NOTE: this will be limited later in cases where we add barriers 2384251662Sdim // to prevent this optimization. 2385251662Sdim // 2386251662Sdim if (level1 && level1 == level2 && level1 == level3 && level1 == level4) { 2387251662Sdim PieceI->setEndLocation(PieceNextI->getEndLocation()); 2388251662Sdim path.erase(NextI); 2389251662Sdim hasChanges = true; 2390251662Sdim continue; 2391251662Sdim } 2392251662Sdim 2393251662Sdim // Rule II. 2394251662Sdim // 2395261991Sdim // Eliminate edges between subexpressions and parent expressions 2396261991Sdim // when the subexpression is consumed. 2397251662Sdim // 2398251662Sdim // NOTE: this will be limited later in cases where we add barriers 2399251662Sdim // to prevent this optimization. 2400251662Sdim // 2401261991Sdim if (s1End && s1End == s2Start && level2) { 2402261991Sdim bool removeEdge = false; 2403261991Sdim // Remove edges into the increment or initialization of a 2404261991Sdim // loop that have no interleaving event. This means that 2405261991Sdim // they aren't interesting. 2406261991Sdim if (isIncrementOrInitInForLoop(s1End, level2)) 2407261991Sdim removeEdge = true; 2408261991Sdim // Next only consider edges that are not anchored on 2409261991Sdim // the condition of a terminator. This are intermediate edges 2410261991Sdim // that we might want to trim. 2411261991Sdim else if (!isConditionForTerminator(level2, s1End)) { 2412261991Sdim // Trim edges on expressions that are consumed by 2413261991Sdim // the parent expression. 2414261991Sdim if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) { 2415261991Sdim removeEdge = true; 2416261991Sdim } 2417261991Sdim // Trim edges where a lexical containment doesn't exist. 2418261991Sdim // For example: 2419261991Sdim // 2420261991Sdim // X -> Y -> Z 2421261991Sdim // 2422261991Sdim // If 'Z' lexically contains Y (it is an ancestor) and 2423261991Sdim // 'X' does not lexically contain Y (it is a descendant OR 2424261991Sdim // it has no lexical relationship at all) then trim. 2425261991Sdim // 2426261991Sdim // This can eliminate edges where we dive into a subexpression 2427261991Sdim // and then pop back out, etc. 2428261991Sdim else if (s1Start && s2End && 2429261991Sdim lexicalContains(PM, s2Start, s2End) && 2430261991Sdim !lexicalContains(PM, s1End, s1Start)) { 2431261991Sdim removeEdge = true; 2432261991Sdim } 2433261991Sdim // Trim edges from a subexpression back to the top level if the 2434261991Sdim // subexpression is on a different line. 2435261991Sdim // 2436261991Sdim // A.1 -> A -> B 2437261991Sdim // becomes 2438261991Sdim // A.1 -> B 2439261991Sdim // 2440261991Sdim // These edges just look ugly and don't usually add anything. 2441261991Sdim else if (s1Start && s2End && 2442261991Sdim lexicalContains(PM, s1Start, s1End)) { 2443261991Sdim SourceRange EdgeRange(PieceI->getEndLocation().asLocation(), 2444261991Sdim PieceI->getStartLocation().asLocation()); 2445261991Sdim if (!getLengthOnSingleLine(SM, EdgeRange).hasValue()) 2446261991Sdim removeEdge = true; 2447261991Sdim } 2448261991Sdim } 2449251662Sdim 2450261991Sdim if (removeEdge) { 2451261991Sdim PieceI->setEndLocation(PieceNextI->getEndLocation()); 2452261991Sdim path.erase(NextI); 2453261991Sdim hasChanges = true; 2454261991Sdim continue; 2455261991Sdim } 2456251662Sdim } 2457251662Sdim 2458261991Sdim // Optimize edges for ObjC fast-enumeration loops. 2459251662Sdim // 2460261991Sdim // (X -> collection) -> (collection -> element) 2461251662Sdim // 2462261991Sdim // becomes: 2463251662Sdim // 2464261991Sdim // (X -> element) 2465261991Sdim if (s1End == s2Start) { 2466261991Sdim const ObjCForCollectionStmt *FS = 2467261991Sdim dyn_cast_or_null<ObjCForCollectionStmt>(level3); 2468261991Sdim if (FS && FS->getCollection()->IgnoreParens() == s2Start && 2469261991Sdim s2End == FS->getElement()) { 2470261991Sdim PieceI->setEndLocation(PieceNextI->getEndLocation()); 2471261991Sdim path.erase(NextI); 2472251662Sdim hasChanges = true; 2473251662Sdim continue; 2474251662Sdim } 2475251662Sdim } 2476251662Sdim 2477251662Sdim // No changes at this index? Move to the next one. 2478251662Sdim ++I; 2479251662Sdim } 2480251662Sdim 2481261991Sdim if (!hasChanges) { 2482261991Sdim // Adjust edges into subexpressions to make them more uniform 2483261991Sdim // and aesthetically pleasing. 2484261991Sdim addContextEdges(path, SM, PM, LC); 2485261991Sdim // Remove "cyclical" edges that include one or more context edges. 2486261991Sdim removeContextCycles(path, SM, PM); 2487261991Sdim // Hoist edges originating from branch conditions to branches 2488261991Sdim // for simple branches. 2489261991Sdim simplifySimpleBranches(path); 2490261991Sdim // Remove any puny edges left over after primary optimization pass. 2491261991Sdim removePunyEdges(path, SM, PM); 2492261991Sdim // Remove identical events. 2493261991Sdim removeIdenticalEvents(path); 2494261991Sdim } 2495261991Sdim 2496251662Sdim return hasChanges; 2497251662Sdim} 2498251662Sdim 2499261991Sdim/// Drop the very first edge in a path, which should be a function entry edge. 2500261991Sdim/// 2501261991Sdim/// If the first edge is not a function entry edge (say, because the first 2502261991Sdim/// statement had an invalid source location), this function does nothing. 2503261991Sdim// FIXME: We should just generate invalid edges anyway and have the optimizer 2504261991Sdim// deal with them. 2505261991Sdimstatic void dropFunctionEntryEdge(PathPieces &Path, 2506261991Sdim LocationContextMap &LCM, 2507261991Sdim SourceManager &SM) { 2508261991Sdim const PathDiagnosticControlFlowPiece *FirstEdge = 2509261991Sdim dyn_cast<PathDiagnosticControlFlowPiece>(Path.front()); 2510261991Sdim if (!FirstEdge) 2511261991Sdim return; 2512261991Sdim 2513261991Sdim const Decl *D = LCM[&Path]->getDecl(); 2514261991Sdim PathDiagnosticLocation EntryLoc = PathDiagnosticLocation::createBegin(D, SM); 2515261991Sdim if (FirstEdge->getStartLocation() != EntryLoc) 2516261991Sdim return; 2517261991Sdim 2518261991Sdim Path.pop_front(); 2519261991Sdim} 2520261991Sdim 2521261991Sdim 2522218887Sdim//===----------------------------------------------------------------------===// 2523218887Sdim// Methods for BugType and subclasses. 2524218887Sdim//===----------------------------------------------------------------------===// 2525261991Sdimvoid BugType::anchor() { } 2526219077Sdim 2527218887Sdimvoid BugType::FlushReports(BugReporter &BR) {} 2528218887Sdim 2529234353Sdimvoid BuiltinBug::anchor() {} 2530234353Sdim 2531218887Sdim//===----------------------------------------------------------------------===// 2532218887Sdim// Methods for BugReport and subclasses. 2533218887Sdim//===----------------------------------------------------------------------===// 2534218887Sdim 2535234353Sdimvoid BugReport::NodeResolver::anchor() {} 2536234353Sdim 2537280031Sdimvoid BugReport::addVisitor(std::unique_ptr<BugReporterVisitor> visitor) { 2538226633Sdim if (!visitor) 2539226633Sdim return; 2540226633Sdim 2541226633Sdim llvm::FoldingSetNodeID ID; 2542226633Sdim visitor->Profile(ID); 2543226633Sdim void *InsertPos; 2544226633Sdim 2545280031Sdim if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) 2546226633Sdim return; 2547226633Sdim 2548280031Sdim CallbacksSet.InsertNode(visitor.get(), InsertPos); 2549280031Sdim Callbacks.push_back(std::move(visitor)); 2550234353Sdim ++ConfigurationChangeToken; 2551226633Sdim} 2552226633Sdim 2553226633SdimBugReport::~BugReport() { 2554239462Sdim while (!interestingSymbols.empty()) { 2555239462Sdim popInterestingSymbolsAndRegions(); 2556239462Sdim } 2557226633Sdim} 2558226633Sdim 2559234353Sdimconst Decl *BugReport::getDeclWithIssue() const { 2560234353Sdim if (DeclWithIssue) 2561234353Sdim return DeclWithIssue; 2562234353Sdim 2563234353Sdim const ExplodedNode *N = getErrorNode(); 2564234353Sdim if (!N) 2565276479Sdim return nullptr; 2566276479Sdim 2567234353Sdim const LocationContext *LC = N->getLocationContext(); 2568234353Sdim return LC->getCurrentStackFrame()->getDecl(); 2569234353Sdim} 2570234353Sdim 2571226633Sdimvoid BugReport::Profile(llvm::FoldingSetNodeID& hash) const { 2572226633Sdim hash.AddPointer(&BT); 2573226633Sdim hash.AddString(Description); 2574249423Sdim PathDiagnosticLocation UL = getUniqueingLocation(); 2575249423Sdim if (UL.isValid()) { 2576249423Sdim UL.Profile(hash); 2577234353Sdim } else if (Location.isValid()) { 2578226633Sdim Location.Profile(hash); 2579226633Sdim } else { 2580226633Sdim assert(ErrorNode); 2581226633Sdim hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode)); 2582226633Sdim } 2583226633Sdim 2584226633Sdim for (SmallVectorImpl<SourceRange>::const_iterator I = 2585226633Sdim Ranges.begin(), E = Ranges.end(); I != E; ++I) { 2586226633Sdim const SourceRange range = *I; 2587226633Sdim if (!range.isValid()) 2588226633Sdim continue; 2589226633Sdim hash.AddInteger(range.getBegin().getRawEncoding()); 2590226633Sdim hash.AddInteger(range.getEnd().getRawEncoding()); 2591226633Sdim } 2592226633Sdim} 2593226633Sdim 2594234353Sdimvoid BugReport::markInteresting(SymbolRef sym) { 2595234353Sdim if (!sym) 2596234353Sdim return; 2597234353Sdim 2598234353Sdim // If the symbol wasn't already in our set, note a configuration change. 2599239462Sdim if (getInterestingSymbols().insert(sym).second) 2600234353Sdim ++ConfigurationChangeToken; 2601234353Sdim 2602234353Sdim if (const SymbolMetadata *meta = dyn_cast<SymbolMetadata>(sym)) 2603239462Sdim getInterestingRegions().insert(meta->getRegion()); 2604234353Sdim} 2605234353Sdim 2606234353Sdimvoid BugReport::markInteresting(const MemRegion *R) { 2607234353Sdim if (!R) 2608234353Sdim return; 2609234353Sdim 2610234353Sdim // If the base region wasn't already in our set, note a configuration change. 2611234353Sdim R = R->getBaseRegion(); 2612239462Sdim if (getInterestingRegions().insert(R).second) 2613234353Sdim ++ConfigurationChangeToken; 2614234353Sdim 2615234353Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 2616239462Sdim getInterestingSymbols().insert(SR->getSymbol()); 2617234353Sdim} 2618234353Sdim 2619234353Sdimvoid BugReport::markInteresting(SVal V) { 2620234353Sdim markInteresting(V.getAsRegion()); 2621234353Sdim markInteresting(V.getAsSymbol()); 2622234353Sdim} 2623234353Sdim 2624243830Sdimvoid BugReport::markInteresting(const LocationContext *LC) { 2625243830Sdim if (!LC) 2626243830Sdim return; 2627243830Sdim InterestingLocationContexts.insert(LC); 2628243830Sdim} 2629243830Sdim 2630239462Sdimbool BugReport::isInteresting(SVal V) { 2631234353Sdim return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol()); 2632234353Sdim} 2633234353Sdim 2634239462Sdimbool BugReport::isInteresting(SymbolRef sym) { 2635234353Sdim if (!sym) 2636234353Sdim return false; 2637234353Sdim // We don't currently consider metadata symbols to be interesting 2638234353Sdim // even if we know their region is interesting. Is that correct behavior? 2639239462Sdim return getInterestingSymbols().count(sym); 2640234353Sdim} 2641234353Sdim 2642239462Sdimbool BugReport::isInteresting(const MemRegion *R) { 2643234353Sdim if (!R) 2644234353Sdim return false; 2645234353Sdim R = R->getBaseRegion(); 2646239462Sdim bool b = getInterestingRegions().count(R); 2647234353Sdim if (b) 2648234353Sdim return true; 2649234353Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 2650239462Sdim return getInterestingSymbols().count(SR->getSymbol()); 2651234353Sdim return false; 2652234353Sdim} 2653234353Sdim 2654243830Sdimbool BugReport::isInteresting(const LocationContext *LC) { 2655243830Sdim if (!LC) 2656243830Sdim return false; 2657243830Sdim return InterestingLocationContexts.count(LC); 2658243830Sdim} 2659243830Sdim 2660239462Sdimvoid BugReport::lazyInitializeInterestingSets() { 2661239462Sdim if (interestingSymbols.empty()) { 2662239462Sdim interestingSymbols.push_back(new Symbols()); 2663239462Sdim interestingRegions.push_back(new Regions()); 2664239462Sdim } 2665239462Sdim} 2666239462Sdim 2667239462SdimBugReport::Symbols &BugReport::getInterestingSymbols() { 2668239462Sdim lazyInitializeInterestingSets(); 2669239462Sdim return *interestingSymbols.back(); 2670239462Sdim} 2671239462Sdim 2672239462SdimBugReport::Regions &BugReport::getInterestingRegions() { 2673239462Sdim lazyInitializeInterestingSets(); 2674239462Sdim return *interestingRegions.back(); 2675239462Sdim} 2676239462Sdim 2677239462Sdimvoid BugReport::pushInterestingSymbolsAndRegions() { 2678239462Sdim interestingSymbols.push_back(new Symbols(getInterestingSymbols())); 2679239462Sdim interestingRegions.push_back(new Regions(getInterestingRegions())); 2680239462Sdim} 2681239462Sdim 2682239462Sdimvoid BugReport::popInterestingSymbolsAndRegions() { 2683261991Sdim delete interestingSymbols.pop_back_val(); 2684261991Sdim delete interestingRegions.pop_back_val(); 2685239462Sdim} 2686239462Sdim 2687226633Sdimconst Stmt *BugReport::getStmt() const { 2688226633Sdim if (!ErrorNode) 2689276479Sdim return nullptr; 2690226633Sdim 2691218887Sdim ProgramPoint ProgP = ErrorNode->getLocation(); 2692276479Sdim const Stmt *S = nullptr; 2693218887Sdim 2694249423Sdim if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) { 2695218887Sdim CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit(); 2696218887Sdim if (BE->getBlock() == &Exit) 2697218887Sdim S = GetPreviousStmt(ErrorNode); 2698218887Sdim } 2699218887Sdim if (!S) 2700251662Sdim S = PathDiagnosticLocation::getStmt(ErrorNode); 2701218887Sdim 2702218887Sdim return S; 2703218887Sdim} 2704218887Sdim 2705226633Sdimstd::pair<BugReport::ranges_iterator, BugReport::ranges_iterator> 2706226633SdimBugReport::getRanges() { 2707226633Sdim // If no custom ranges, add the range of the statement corresponding to 2708226633Sdim // the error node. 2709226633Sdim if (Ranges.empty()) { 2710226633Sdim if (const Expr *E = dyn_cast_or_null<Expr>(getStmt())) 2711226633Sdim addRange(E->getSourceRange()); 2712226633Sdim else 2713226633Sdim return std::make_pair(ranges_iterator(), ranges_iterator()); 2714226633Sdim } 2715218887Sdim 2716226633Sdim // User-specified absence of range info. 2717226633Sdim if (Ranges.size() == 1 && !Ranges.begin()->isValid()) 2718226633Sdim return std::make_pair(ranges_iterator(), ranges_iterator()); 2719218887Sdim 2720226633Sdim return std::make_pair(Ranges.begin(), Ranges.end()); 2721226633Sdim} 2722218887Sdim 2723226633SdimPathDiagnosticLocation BugReport::getLocation(const SourceManager &SM) const { 2724226633Sdim if (ErrorNode) { 2725226633Sdim assert(!Location.isValid() && 2726226633Sdim "Either Location or ErrorNode should be specified but not both."); 2727251662Sdim return PathDiagnosticLocation::createEndOfPath(ErrorNode, SM); 2728226633Sdim } 2729218887Sdim 2730276479Sdim assert(Location.isValid()); 2731276479Sdim return Location; 2732218887Sdim} 2733218887Sdim 2734218887Sdim//===----------------------------------------------------------------------===// 2735218887Sdim// Methods for BugReporter and subclasses. 2736218887Sdim//===----------------------------------------------------------------------===// 2737218887Sdim 2738234353SdimBugReportEquivClass::~BugReportEquivClass() { } 2739218887SdimGRBugReporter::~GRBugReporter() { } 2740218887SdimBugReporterData::~BugReporterData() {} 2741218887Sdim 2742218887SdimExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); } 2743218887Sdim 2744226633SdimProgramStateManager& 2745218887SdimGRBugReporter::getStateManager() { return Eng.getStateManager(); } 2746218887Sdim 2747226633SdimBugReporter::~BugReporter() { 2748226633Sdim FlushReports(); 2749218887Sdim 2750226633Sdim // Free the bug reports we are tracking. 2751226633Sdim typedef std::vector<BugReportEquivClass *> ContTy; 2752226633Sdim for (ContTy::iterator I = EQClassesVector.begin(), E = EQClassesVector.end(); 2753226633Sdim I != E; ++I) { 2754226633Sdim delete *I; 2755226633Sdim } 2756226633Sdim} 2757226633Sdim 2758218887Sdimvoid BugReporter::FlushReports() { 2759218887Sdim if (BugTypes.isEmpty()) 2760218887Sdim return; 2761218887Sdim 2762218887Sdim // First flush the warnings for each BugType. This may end up creating new 2763219077Sdim // warnings and new BugTypes. 2764219077Sdim // FIXME: Only NSErrorChecker needs BugType's FlushReports. 2765219077Sdim // Turn NSErrorChecker into a proper checker and remove this. 2766226633Sdim SmallVector<const BugType*, 16> bugTypes; 2767218887Sdim for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I) 2768219077Sdim bugTypes.push_back(*I); 2769261991Sdim for (SmallVectorImpl<const BugType *>::iterator 2770219077Sdim I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I) 2771218887Sdim const_cast<BugType*>(*I)->FlushReports(*this); 2772218887Sdim 2773239462Sdim // We need to flush reports in deterministic order to ensure the order 2774239462Sdim // of the reports is consistent between runs. 2775239462Sdim typedef std::vector<BugReportEquivClass *> ContVecTy; 2776239462Sdim for (ContVecTy::iterator EI=EQClassesVector.begin(), EE=EQClassesVector.end(); 2777239462Sdim EI != EE; ++EI){ 2778239462Sdim BugReportEquivClass& EQ = **EI; 2779219077Sdim FlushReport(EQ); 2780219077Sdim } 2781218887Sdim 2782219077Sdim // BugReporter owns and deletes only BugTypes created implicitly through 2783219077Sdim // EmitBasicReport. 2784219077Sdim // FIXME: There are leaks from checkers that assume that the BugTypes they 2785219077Sdim // create will be destroyed by the BugReporter. 2786276479Sdim llvm::DeleteContainerSeconds(StrBugTypes); 2787218887Sdim 2788218887Sdim // Remove all references to the BugType objects. 2789218887Sdim BugTypes = F.getEmptySet(); 2790218887Sdim} 2791218887Sdim 2792218887Sdim//===----------------------------------------------------------------------===// 2793218887Sdim// PathDiagnostics generation. 2794218887Sdim//===----------------------------------------------------------------------===// 2795218887Sdim 2796249423Sdimnamespace { 2797249423Sdim/// A wrapper around a report graph, which contains only a single path, and its 2798249423Sdim/// node maps. 2799249423Sdimclass ReportGraph { 2800249423Sdimpublic: 2801249423Sdim InterExplodedGraphMap BackMap; 2802276479Sdim std::unique_ptr<ExplodedGraph> Graph; 2803249423Sdim const ExplodedNode *ErrorNode; 2804249423Sdim size_t Index; 2805249423Sdim}; 2806218887Sdim 2807249423Sdim/// A wrapper around a trimmed graph and its node maps. 2808249423Sdimclass TrimmedGraph { 2809249423Sdim InterExplodedGraphMap InverseMap; 2810218887Sdim 2811249423Sdim typedef llvm::DenseMap<const ExplodedNode *, unsigned> PriorityMapTy; 2812249423Sdim PriorityMapTy PriorityMap; 2813218887Sdim 2814249423Sdim typedef std::pair<const ExplodedNode *, size_t> NodeIndexPair; 2815249423Sdim SmallVector<NodeIndexPair, 32> ReportNodes; 2816218887Sdim 2817276479Sdim std::unique_ptr<ExplodedGraph> G; 2818249423Sdim 2819249423Sdim /// A helper class for sorting ExplodedNodes by priority. 2820249423Sdim template <bool Descending> 2821249423Sdim class PriorityCompare { 2822249423Sdim const PriorityMapTy &PriorityMap; 2823249423Sdim 2824249423Sdim public: 2825249423Sdim PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {} 2826249423Sdim 2827249423Sdim bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const { 2828249423Sdim PriorityMapTy::const_iterator LI = PriorityMap.find(LHS); 2829249423Sdim PriorityMapTy::const_iterator RI = PriorityMap.find(RHS); 2830249423Sdim PriorityMapTy::const_iterator E = PriorityMap.end(); 2831249423Sdim 2832249423Sdim if (LI == E) 2833249423Sdim return Descending; 2834249423Sdim if (RI == E) 2835249423Sdim return !Descending; 2836249423Sdim 2837249423Sdim return Descending ? LI->second > RI->second 2838249423Sdim : LI->second < RI->second; 2839249423Sdim } 2840249423Sdim 2841249423Sdim bool operator()(const NodeIndexPair &LHS, const NodeIndexPair &RHS) const { 2842249423Sdim return (*this)(LHS.first, RHS.first); 2843249423Sdim } 2844249423Sdim }; 2845249423Sdim 2846249423Sdimpublic: 2847249423Sdim TrimmedGraph(const ExplodedGraph *OriginalGraph, 2848249423Sdim ArrayRef<const ExplodedNode *> Nodes); 2849249423Sdim 2850249423Sdim bool popNextReportGraph(ReportGraph &GraphWrapper); 2851249423Sdim}; 2852249423Sdim} 2853249423Sdim 2854249423SdimTrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph, 2855249423Sdim ArrayRef<const ExplodedNode *> Nodes) { 2856249423Sdim // The trimmed graph is created in the body of the constructor to ensure 2857249423Sdim // that the DenseMaps have been initialized already. 2858249423Sdim InterExplodedGraphMap ForwardMap; 2859280031Sdim G = OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap); 2860249423Sdim 2861218887Sdim // Find the (first) error node in the trimmed graph. We just need to consult 2862249423Sdim // the node map which maps from nodes in the original graph to nodes 2863218887Sdim // in the new graph. 2864249423Sdim llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes; 2865218887Sdim 2866249423Sdim for (unsigned i = 0, count = Nodes.size(); i < count; ++i) { 2867249423Sdim if (const ExplodedNode *NewNode = ForwardMap.lookup(Nodes[i])) { 2868249423Sdim ReportNodes.push_back(std::make_pair(NewNode, i)); 2869249423Sdim RemainingNodes.insert(NewNode); 2870218887Sdim } 2871218887Sdim } 2872218887Sdim 2873249423Sdim assert(!RemainingNodes.empty() && "No error node found in the trimmed graph"); 2874218887Sdim 2875249423Sdim // Perform a forward BFS to find all the shortest paths. 2876249423Sdim std::queue<const ExplodedNode *> WS; 2877218887Sdim 2878249423Sdim assert(G->num_roots() == 1); 2879249423Sdim WS.push(*G->roots_begin()); 2880249423Sdim unsigned Priority = 0; 2881218887Sdim 2882218887Sdim while (!WS.empty()) { 2883226633Sdim const ExplodedNode *Node = WS.front(); 2884218887Sdim WS.pop(); 2885218887Sdim 2886249423Sdim PriorityMapTy::iterator PriorityEntry; 2887249423Sdim bool IsNew; 2888276479Sdim std::tie(PriorityEntry, IsNew) = 2889249423Sdim PriorityMap.insert(std::make_pair(Node, Priority)); 2890249423Sdim ++Priority; 2891249423Sdim 2892249423Sdim if (!IsNew) { 2893249423Sdim assert(PriorityEntry->second <= Priority); 2894218887Sdim continue; 2895249423Sdim } 2896218887Sdim 2897249423Sdim if (RemainingNodes.erase(Node)) 2898249423Sdim if (RemainingNodes.empty()) 2899249423Sdim break; 2900218887Sdim 2901249423Sdim for (ExplodedNode::const_pred_iterator I = Node->succ_begin(), 2902249423Sdim E = Node->succ_end(); 2903249423Sdim I != E; ++I) 2904218887Sdim WS.push(*I); 2905218887Sdim } 2906218887Sdim 2907249423Sdim // Sort the error paths from longest to shortest. 2908249423Sdim std::sort(ReportNodes.begin(), ReportNodes.end(), 2909249423Sdim PriorityCompare<true>(PriorityMap)); 2910249423Sdim} 2911218887Sdim 2912249423Sdimbool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) { 2913249423Sdim if (ReportNodes.empty()) 2914249423Sdim return false; 2915218887Sdim 2916249423Sdim const ExplodedNode *OrigN; 2917276479Sdim std::tie(OrigN, GraphWrapper.Index) = ReportNodes.pop_back_val(); 2918249423Sdim assert(PriorityMap.find(OrigN) != PriorityMap.end() && 2919249423Sdim "error node not accessible from root"); 2920218887Sdim 2921249423Sdim // Create a new graph with a single path. This is the graph 2922249423Sdim // that will be returned to the caller. 2923280031Sdim auto GNew = llvm::make_unique<ExplodedGraph>(); 2924249423Sdim GraphWrapper.BackMap.clear(); 2925249423Sdim 2926249423Sdim // Now walk from the error node up the BFS path, always taking the 2927249423Sdim // predeccessor with the lowest number. 2928276479Sdim ExplodedNode *Succ = nullptr; 2929249423Sdim while (true) { 2930218887Sdim // Create the equivalent node in the new graph with the same state 2931218887Sdim // and location. 2932251662Sdim ExplodedNode *NewN = GNew->getNode(OrigN->getLocation(), OrigN->getState(), 2933251662Sdim OrigN->isSink()); 2934218887Sdim 2935218887Sdim // Store the mapping to the original node. 2936249423Sdim InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN); 2937218887Sdim assert(IMitr != InverseMap.end() && "No mapping to original node."); 2938249423Sdim GraphWrapper.BackMap[NewN] = IMitr->second; 2939218887Sdim 2940218887Sdim // Link up the new node with the previous node. 2941249423Sdim if (Succ) 2942249423Sdim Succ->addPredecessor(NewN, *GNew); 2943249423Sdim else 2944249423Sdim GraphWrapper.ErrorNode = NewN; 2945218887Sdim 2946249423Sdim Succ = NewN; 2947218887Sdim 2948218887Sdim // Are we at the final node? 2949249423Sdim if (OrigN->pred_empty()) { 2950249423Sdim GNew->addRoot(NewN); 2951218887Sdim break; 2952218887Sdim } 2953218887Sdim 2954249423Sdim // Find the next predeccessor node. We choose the node that is marked 2955249423Sdim // with the lowest BFS number. 2956249423Sdim OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(), 2957249423Sdim PriorityCompare<false>(PriorityMap)); 2958218887Sdim } 2959218887Sdim 2960280031Sdim GraphWrapper.Graph = std::move(GNew); 2961280031Sdim 2962249423Sdim return true; 2963218887Sdim} 2964218887Sdim 2965249423Sdim 2966218887Sdim/// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object 2967218887Sdim/// and collapses PathDiagosticPieces that are expanded by macros. 2968234353Sdimstatic void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) { 2969234353Sdim typedef std::vector<std::pair<IntrusiveRefCntPtr<PathDiagnosticMacroPiece>, 2970234353Sdim SourceLocation> > MacroStackTy; 2971218887Sdim 2972234353Sdim typedef std::vector<IntrusiveRefCntPtr<PathDiagnosticPiece> > 2973218887Sdim PiecesTy; 2974218887Sdim 2975218887Sdim MacroStackTy MacroStack; 2976218887Sdim PiecesTy Pieces; 2977218887Sdim 2978234353Sdim for (PathPieces::const_iterator I = path.begin(), E = path.end(); 2979234353Sdim I!=E; ++I) { 2980234353Sdim 2981276479Sdim PathDiagnosticPiece *piece = I->get(); 2982234353Sdim 2983234353Sdim // Recursively compact calls. 2984234353Sdim if (PathDiagnosticCallPiece *call=dyn_cast<PathDiagnosticCallPiece>(piece)){ 2985234353Sdim CompactPathDiagnostic(call->path, SM); 2986234353Sdim } 2987234353Sdim 2988218887Sdim // Get the location of the PathDiagnosticPiece. 2989234353Sdim const FullSourceLoc Loc = piece->getLocation().asLocation(); 2990218887Sdim 2991218887Sdim // Determine the instantiation location, which is the location we group 2992218887Sdim // related PathDiagnosticPieces. 2993218887Sdim SourceLocation InstantiationLoc = Loc.isMacroID() ? 2994226633Sdim SM.getExpansionLoc(Loc) : 2995218887Sdim SourceLocation(); 2996218887Sdim 2997218887Sdim if (Loc.isFileID()) { 2998218887Sdim MacroStack.clear(); 2999234353Sdim Pieces.push_back(piece); 3000218887Sdim continue; 3001218887Sdim } 3002218887Sdim 3003218887Sdim assert(Loc.isMacroID()); 3004218887Sdim 3005218887Sdim // Is the PathDiagnosticPiece within the same macro group? 3006218887Sdim if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) { 3007234353Sdim MacroStack.back().first->subPieces.push_back(piece); 3008218887Sdim continue; 3009218887Sdim } 3010218887Sdim 3011218887Sdim // We aren't in the same group. Are we descending into a new macro 3012218887Sdim // or are part of an old one? 3013234353Sdim IntrusiveRefCntPtr<PathDiagnosticMacroPiece> MacroGroup; 3014218887Sdim 3015218887Sdim SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ? 3016226633Sdim SM.getExpansionLoc(Loc) : 3017218887Sdim SourceLocation(); 3018218887Sdim 3019218887Sdim // Walk the entire macro stack. 3020218887Sdim while (!MacroStack.empty()) { 3021218887Sdim if (InstantiationLoc == MacroStack.back().second) { 3022218887Sdim MacroGroup = MacroStack.back().first; 3023218887Sdim break; 3024218887Sdim } 3025218887Sdim 3026218887Sdim if (ParentInstantiationLoc == MacroStack.back().second) { 3027218887Sdim MacroGroup = MacroStack.back().first; 3028218887Sdim break; 3029218887Sdim } 3030218887Sdim 3031218887Sdim MacroStack.pop_back(); 3032218887Sdim } 3033218887Sdim 3034218887Sdim if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) { 3035218887Sdim // Create a new macro group and add it to the stack. 3036226633Sdim PathDiagnosticMacroPiece *NewGroup = 3037226633Sdim new PathDiagnosticMacroPiece( 3038234353Sdim PathDiagnosticLocation::createSingleLocation(piece->getLocation())); 3039218887Sdim 3040218887Sdim if (MacroGroup) 3041234353Sdim MacroGroup->subPieces.push_back(NewGroup); 3042218887Sdim else { 3043218887Sdim assert(InstantiationLoc.isFileID()); 3044218887Sdim Pieces.push_back(NewGroup); 3045218887Sdim } 3046218887Sdim 3047218887Sdim MacroGroup = NewGroup; 3048218887Sdim MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc)); 3049218887Sdim } 3050218887Sdim 3051218887Sdim // Finally, add the PathDiagnosticPiece to the group. 3052234353Sdim MacroGroup->subPieces.push_back(piece); 3053218887Sdim } 3054218887Sdim 3055218887Sdim // Now take the pieces and construct a new PathDiagnostic. 3056234353Sdim path.clear(); 3057218887Sdim 3058234353Sdim for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I) 3059234353Sdim path.push_back(*I); 3060218887Sdim} 3061218887Sdim 3062243830Sdimbool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD, 3063239462Sdim PathDiagnosticConsumer &PC, 3064239462Sdim ArrayRef<BugReport *> &bugReports) { 3065243830Sdim assert(!bugReports.empty()); 3066218887Sdim 3067243830Sdim bool HasValid = false; 3068249423Sdim bool HasInvalid = false; 3069249423Sdim SmallVector<const ExplodedNode *, 32> errorNodes; 3070239462Sdim for (ArrayRef<BugReport*>::iterator I = bugReports.begin(), 3071239462Sdim E = bugReports.end(); I != E; ++I) { 3072243830Sdim if ((*I)->isValid()) { 3073243830Sdim HasValid = true; 3074218887Sdim errorNodes.push_back((*I)->getErrorNode()); 3075243830Sdim } else { 3076249423Sdim // Keep the errorNodes list in sync with the bugReports list. 3077249423Sdim HasInvalid = true; 3078276479Sdim errorNodes.push_back(nullptr); 3079243830Sdim } 3080218887Sdim } 3081218887Sdim 3082249423Sdim // If all the reports have been marked invalid by a previous path generation, 3083249423Sdim // we're done. 3084243830Sdim if (!HasValid) 3085243830Sdim return false; 3086243830Sdim 3087249423Sdim typedef PathDiagnosticConsumer::PathGenerationScheme PathGenerationScheme; 3088249423Sdim PathGenerationScheme ActiveScheme = PC.getGenerationScheme(); 3089218887Sdim 3090251662Sdim if (ActiveScheme == PathDiagnosticConsumer::Extensive) { 3091261991Sdim AnalyzerOptions &options = getAnalyzerOptions(); 3092261991Sdim if (options.getBooleanOption("path-diagnostics-alternate", true)) { 3093251662Sdim ActiveScheme = PathDiagnosticConsumer::AlternateExtensive; 3094251662Sdim } 3095251662Sdim } 3096251662Sdim 3097249423Sdim TrimmedGraph TrimG(&getGraph(), errorNodes); 3098249423Sdim ReportGraph ErrorGraph; 3099218887Sdim 3100249423Sdim while (TrimG.popNextReportGraph(ErrorGraph)) { 3101249423Sdim // Find the BugReport with the original location. 3102249423Sdim assert(ErrorGraph.Index < bugReports.size()); 3103249423Sdim BugReport *R = bugReports[ErrorGraph.Index]; 3104249423Sdim assert(R && "No original report found for sliced graph."); 3105249423Sdim assert(R->isValid() && "Report selected by trimmed graph marked invalid."); 3106218887Sdim 3107249423Sdim // Start building the path diagnostic... 3108249423Sdim PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, &PC); 3109249423Sdim const ExplodedNode *N = ErrorGraph.ErrorNode; 3110218887Sdim 3111249423Sdim // Register additional node visitors. 3112280031Sdim R->addVisitor(llvm::make_unique<NilReceiverBRVisitor>()); 3113280031Sdim R->addVisitor(llvm::make_unique<ConditionBRVisitor>()); 3114280031Sdim R->addVisitor(llvm::make_unique<LikelyFalsePositiveSuppressionBRVisitor>()); 3115226633Sdim 3116249423Sdim BugReport::VisitorList visitors; 3117249423Sdim unsigned origReportConfigToken, finalReportConfigToken; 3118251662Sdim LocationContextMap LCM; 3119234353Sdim 3120249423Sdim // While generating diagnostics, it's possible the visitors will decide 3121249423Sdim // new symbols and regions are interesting, or add other visitors based on 3122249423Sdim // the information they find. If they do, we need to regenerate the path 3123249423Sdim // based on our new report configuration. 3124249423Sdim do { 3125249423Sdim // Get a clean copy of all the visitors. 3126249423Sdim for (BugReport::visitor_iterator I = R->visitor_begin(), 3127249423Sdim E = R->visitor_end(); I != E; ++I) 3128249423Sdim visitors.push_back((*I)->clone()); 3129234353Sdim 3130249423Sdim // Clear out the active path from any previous work. 3131249423Sdim PD.resetPath(); 3132249423Sdim origReportConfigToken = R->getConfigurationChangeToken(); 3133234353Sdim 3134249423Sdim // Generate the very last diagnostic piece - the piece is visible before 3135249423Sdim // the trace is expanded. 3136276479Sdim std::unique_ptr<PathDiagnosticPiece> LastPiece; 3137243830Sdim for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end(); 3138249423Sdim I != E; ++I) { 3139280031Sdim if (std::unique_ptr<PathDiagnosticPiece> Piece = 3140280031Sdim (*I)->getEndPath(PDB, N, *R)) { 3141243830Sdim assert (!LastPiece && 3142249423Sdim "There can only be one final piece in a diagnostic."); 3143280031Sdim LastPiece = std::move(Piece); 3144243830Sdim } 3145234353Sdim } 3146249423Sdim 3147249423Sdim if (ActiveScheme != PathDiagnosticConsumer::None) { 3148249423Sdim if (!LastPiece) 3149280031Sdim LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R); 3150249423Sdim assert(LastPiece); 3151280031Sdim PD.setEndOfPath(std::move(LastPiece)); 3152249423Sdim } 3153218887Sdim 3154251662Sdim // Make sure we get a clean location context map so we don't 3155251662Sdim // hold onto old mappings. 3156251662Sdim LCM.clear(); 3157251662Sdim 3158249423Sdim switch (ActiveScheme) { 3159251662Sdim case PathDiagnosticConsumer::AlternateExtensive: 3160251662Sdim GenerateAlternateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors); 3161251662Sdim break; 3162249423Sdim case PathDiagnosticConsumer::Extensive: 3163251662Sdim GenerateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors); 3164249423Sdim break; 3165249423Sdim case PathDiagnosticConsumer::Minimal: 3166251662Sdim GenerateMinimalPathDiagnostic(PD, PDB, N, LCM, visitors); 3167249423Sdim break; 3168249423Sdim case PathDiagnosticConsumer::None: 3169249423Sdim GenerateVisitorsOnlyPathDiagnostic(PD, PDB, N, visitors); 3170249423Sdim break; 3171243830Sdim } 3172234353Sdim 3173249423Sdim // Clean up the visitors we used. 3174280031Sdim visitors.clear(); 3175234353Sdim 3176249423Sdim // Did anything change while generating this path? 3177249423Sdim finalReportConfigToken = R->getConfigurationChangeToken(); 3178249423Sdim } while (finalReportConfigToken != origReportConfigToken); 3179234353Sdim 3180249423Sdim if (!R->isValid()) 3181249423Sdim continue; 3182243830Sdim 3183249423Sdim // Finally, prune the diagnostic path of uninteresting stuff. 3184249423Sdim if (!PD.path.empty()) { 3185261991Sdim if (R->shouldPrunePath() && getAnalyzerOptions().shouldPrunePaths()) { 3186251662Sdim bool stillHasNotes = removeUnneededCalls(PD.getMutablePieces(), R, LCM); 3187249423Sdim assert(stillHasNotes); 3188249423Sdim (void)stillHasNotes; 3189249423Sdim } 3190249423Sdim 3191261991Sdim // Redirect all call pieces to have valid locations. 3192249423Sdim adjustCallLocations(PD.getMutablePieces()); 3193261991Sdim removePiecesWithInvalidLocations(PD.getMutablePieces()); 3194251662Sdim 3195251662Sdim if (ActiveScheme == PathDiagnosticConsumer::AlternateExtensive) { 3196261991Sdim SourceManager &SM = getSourceManager(); 3197261991Sdim 3198261991Sdim // Reduce the number of edges from a very conservative set 3199261991Sdim // to an aesthetically pleasing subset that conveys the 3200261991Sdim // necessary information. 3201251662Sdim OptimizedCallsSet OCS; 3202261991Sdim while (optimizeEdges(PD.getMutablePieces(), SM, OCS, LCM)) {} 3203261991Sdim 3204261991Sdim // Drop the very first function-entry edge. It's not really necessary 3205261991Sdim // for top-level functions. 3206261991Sdim dropFunctionEntryEdge(PD.getMutablePieces(), LCM, SM); 3207251662Sdim } 3208261991Sdim 3209261991Sdim // Remove messages that are basically the same, and edges that may not 3210261991Sdim // make sense. 3211261991Sdim // We have to do this after edge optimization in the Extensive mode. 3212261991Sdim removeRedundantMsgs(PD.getMutablePieces()); 3213261991Sdim removeEdgesToDefaultInitializers(PD.getMutablePieces()); 3214243830Sdim } 3215249423Sdim 3216249423Sdim // We found a report and didn't suppress it. 3217249423Sdim return true; 3218239462Sdim } 3219243830Sdim 3220249423Sdim // We suppressed all the reports in this equivalence class. 3221249423Sdim assert(!HasInvalid && "Inconsistent suppression"); 3222249423Sdim (void)HasInvalid; 3223249423Sdim return false; 3224218887Sdim} 3225218887Sdim 3226218887Sdimvoid BugReporter::Register(BugType *BT) { 3227218887Sdim BugTypes = F.add(BugTypes, BT); 3228218887Sdim} 3229218887Sdim 3230243830Sdimvoid BugReporter::emitReport(BugReport* R) { 3231276479Sdim // To guarantee memory release. 3232276479Sdim std::unique_ptr<BugReport> UniqueR(R); 3233276479Sdim 3234261991Sdim if (const ExplodedNode *E = R->getErrorNode()) { 3235280031Sdim const AnalysisDeclContext *DeclCtx = 3236280031Sdim E->getLocationContext()->getAnalysisDeclContext(); 3237280031Sdim // The source of autosynthesized body can be handcrafted AST or a model 3238280031Sdim // file. The locations from handcrafted ASTs have no valid source locations 3239280031Sdim // and have to be discarded. Locations from model files should be preserved 3240280031Sdim // for processing and reporting. 3241280031Sdim if (DeclCtx->isBodyAutosynthesized() && 3242280031Sdim !DeclCtx->isBodyAutosynthesizedFromModelFile()) 3243261991Sdim return; 3244261991Sdim } 3245261991Sdim 3246261991Sdim bool ValidSourceLoc = R->getLocation(getSourceManager()).isValid(); 3247261991Sdim assert(ValidSourceLoc); 3248261991Sdim // If we mess up in a release build, we'd still prefer to just drop the bug 3249261991Sdim // instead of trying to go on. 3250261991Sdim if (!ValidSourceLoc) 3251261991Sdim return; 3252261991Sdim 3253218887Sdim // Compute the bug report's hash to determine its equivalence class. 3254218887Sdim llvm::FoldingSetNodeID ID; 3255218887Sdim R->Profile(ID); 3256218887Sdim 3257218887Sdim // Lookup the equivance class. If there isn't one, create it. 3258218887Sdim BugType& BT = R->getBugType(); 3259218887Sdim Register(&BT); 3260218887Sdim void *InsertPos; 3261219077Sdim BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos); 3262218887Sdim 3263218887Sdim if (!EQ) { 3264280031Sdim EQ = new BugReportEquivClass(std::move(UniqueR)); 3265219077Sdim EQClasses.InsertNode(EQ, InsertPos); 3266226633Sdim EQClassesVector.push_back(EQ); 3267280031Sdim } else 3268280031Sdim EQ->AddReport(std::move(UniqueR)); 3269218887Sdim} 3270218887Sdim 3271218887Sdim 3272218887Sdim//===----------------------------------------------------------------------===// 3273218887Sdim// Emitting reports in equivalence classes. 3274218887Sdim//===----------------------------------------------------------------------===// 3275218887Sdim 3276218887Sdimnamespace { 3277218887Sdimstruct FRIEC_WLItem { 3278218887Sdim const ExplodedNode *N; 3279218887Sdim ExplodedNode::const_succ_iterator I, E; 3280218887Sdim 3281218887Sdim FRIEC_WLItem(const ExplodedNode *n) 3282218887Sdim : N(n), I(N->succ_begin()), E(N->succ_end()) {} 3283218887Sdim}; 3284218887Sdim} 3285218887Sdim 3286218887Sdimstatic BugReport * 3287218887SdimFindReportInEquivalenceClass(BugReportEquivClass& EQ, 3288226633Sdim SmallVectorImpl<BugReport*> &bugReports) { 3289218887Sdim 3290218887Sdim BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end(); 3291218887Sdim assert(I != E); 3292234353Sdim BugType& BT = I->getBugType(); 3293218887Sdim 3294218887Sdim // If we don't need to suppress any of the nodes because they are 3295218887Sdim // post-dominated by a sink, simply add all the nodes in the equivalence class 3296218887Sdim // to 'Nodes'. Any of the reports will serve as a "representative" report. 3297218887Sdim if (!BT.isSuppressOnSink()) { 3298234353Sdim BugReport *R = I; 3299218887Sdim for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) { 3300226633Sdim const ExplodedNode *N = I->getErrorNode(); 3301218887Sdim if (N) { 3302234353Sdim R = I; 3303218887Sdim bugReports.push_back(R); 3304218887Sdim } 3305218887Sdim } 3306218887Sdim return R; 3307218887Sdim } 3308218887Sdim 3309218887Sdim // For bug reports that should be suppressed when all paths are post-dominated 3310218887Sdim // by a sink node, iterate through the reports in the equivalence class 3311218887Sdim // until we find one that isn't post-dominated (if one exists). We use a 3312218887Sdim // DFS traversal of the ExplodedGraph to find a non-sink node. We could write 3313218887Sdim // this as a recursive function, but we don't want to risk blowing out the 3314218887Sdim // stack for very long paths. 3315276479Sdim BugReport *exampleReport = nullptr; 3316218887Sdim 3317218887Sdim for (; I != E; ++I) { 3318234353Sdim const ExplodedNode *errorNode = I->getErrorNode(); 3319218887Sdim 3320218887Sdim if (!errorNode) 3321218887Sdim continue; 3322218887Sdim if (errorNode->isSink()) { 3323226633Sdim llvm_unreachable( 3324218887Sdim "BugType::isSuppressSink() should not be 'true' for sink end nodes"); 3325218887Sdim } 3326218887Sdim // No successors? By definition this nodes isn't post-dominated by a sink. 3327218887Sdim if (errorNode->succ_empty()) { 3328234353Sdim bugReports.push_back(I); 3329218887Sdim if (!exampleReport) 3330234353Sdim exampleReport = I; 3331218887Sdim continue; 3332218887Sdim } 3333218887Sdim 3334218887Sdim // At this point we know that 'N' is not a sink and it has at least one 3335218887Sdim // successor. Use a DFS worklist to find a non-sink end-of-path node. 3336218887Sdim typedef FRIEC_WLItem WLItem; 3337226633Sdim typedef SmallVector<WLItem, 10> DFSWorkList; 3338218887Sdim llvm::DenseMap<const ExplodedNode *, unsigned> Visited; 3339218887Sdim 3340218887Sdim DFSWorkList WL; 3341218887Sdim WL.push_back(errorNode); 3342218887Sdim Visited[errorNode] = 1; 3343218887Sdim 3344218887Sdim while (!WL.empty()) { 3345218887Sdim WLItem &WI = WL.back(); 3346218887Sdim assert(!WI.N->succ_empty()); 3347218887Sdim 3348218887Sdim for (; WI.I != WI.E; ++WI.I) { 3349218887Sdim const ExplodedNode *Succ = *WI.I; 3350218887Sdim // End-of-path node? 3351218887Sdim if (Succ->succ_empty()) { 3352218887Sdim // If we found an end-of-path node that is not a sink. 3353218887Sdim if (!Succ->isSink()) { 3354234353Sdim bugReports.push_back(I); 3355218887Sdim if (!exampleReport) 3356234353Sdim exampleReport = I; 3357218887Sdim WL.clear(); 3358218887Sdim break; 3359218887Sdim } 3360218887Sdim // Found a sink? Continue on to the next successor. 3361218887Sdim continue; 3362218887Sdim } 3363218887Sdim // Mark the successor as visited. If it hasn't been explored, 3364218887Sdim // enqueue it to the DFS worklist. 3365218887Sdim unsigned &mark = Visited[Succ]; 3366218887Sdim if (!mark) { 3367218887Sdim mark = 1; 3368218887Sdim WL.push_back(Succ); 3369218887Sdim break; 3370218887Sdim } 3371218887Sdim } 3372218887Sdim 3373218887Sdim // The worklist may have been cleared at this point. First 3374218887Sdim // check if it is empty before checking the last item. 3375218887Sdim if (!WL.empty() && &WL.back() == &WI) 3376218887Sdim WL.pop_back(); 3377218887Sdim } 3378218887Sdim } 3379218887Sdim 3380218887Sdim // ExampleReport will be NULL if all the nodes in the equivalence class 3381218887Sdim // were post-dominated by sinks. 3382218887Sdim return exampleReport; 3383218887Sdim} 3384218887Sdim 3385239462Sdimvoid BugReporter::FlushReport(BugReportEquivClass& EQ) { 3386239462Sdim SmallVector<BugReport*, 10> bugReports; 3387239462Sdim BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports); 3388239462Sdim if (exampleReport) { 3389276479Sdim for (PathDiagnosticConsumer *PDC : getPathDiagnosticConsumers()) { 3390276479Sdim FlushReport(exampleReport, *PDC, bugReports); 3391239462Sdim } 3392218887Sdim } 3393218887Sdim} 3394218887Sdim 3395239462Sdimvoid BugReporter::FlushReport(BugReport *exampleReport, 3396239462Sdim PathDiagnosticConsumer &PD, 3397239462Sdim ArrayRef<BugReport*> bugReports) { 3398218887Sdim 3399218887Sdim // FIXME: Make sure we use the 'R' for the path that was actually used. 3400218887Sdim // Probably doesn't make a difference in practice. 3401218887Sdim BugType& BT = exampleReport->getBugType(); 3402218887Sdim 3403276479Sdim std::unique_ptr<PathDiagnostic> D(new PathDiagnostic( 3404276479Sdim exampleReport->getBugType().getCheckName(), 3405276479Sdim exampleReport->getDeclWithIssue(), exampleReport->getBugType().getName(), 3406276479Sdim exampleReport->getDescription(), 3407276479Sdim exampleReport->getShortDescription(/*Fallback=*/false), BT.getCategory(), 3408276479Sdim exampleReport->getUniqueingLocation(), 3409276479Sdim exampleReport->getUniqueingDecl())); 3410218887Sdim 3411249423Sdim MaxBugClassSize = std::max(bugReports.size(), 3412249423Sdim static_cast<size_t>(MaxBugClassSize)); 3413249423Sdim 3414239462Sdim // Generate the full path diagnostic, using the generation scheme 3415243830Sdim // specified by the PathDiagnosticConsumer. Note that we have to generate 3416243830Sdim // path diagnostics even for consumers which do not support paths, because 3417243830Sdim // the BugReporterVisitors may mark this bug as a false positive. 3418243830Sdim if (!bugReports.empty()) 3419243830Sdim if (!generatePathDiagnostic(*D.get(), PD, bugReports)) 3420243830Sdim return; 3421218887Sdim 3422249423Sdim MaxValidBugClassSize = std::max(bugReports.size(), 3423249423Sdim static_cast<size_t>(MaxValidBugClassSize)); 3424249423Sdim 3425261991Sdim // Examine the report and see if the last piece is in a header. Reset the 3426261991Sdim // report location to the last piece in the main source file. 3427261991Sdim AnalyzerOptions& Opts = getAnalyzerOptions(); 3428261991Sdim if (Opts.shouldReportIssuesInMainSourceFile() && !Opts.AnalyzeAll) 3429261991Sdim D->resetDiagnosticLocationToMainFile(); 3430261991Sdim 3431239462Sdim // If the path is empty, generate a single step path with the location 3432239462Sdim // of the issue. 3433234353Sdim if (D->path.empty()) { 3434239462Sdim PathDiagnosticLocation L = exampleReport->getLocation(getSourceManager()); 3435280031Sdim auto piece = llvm::make_unique<PathDiagnosticEventPiece>( 3436280031Sdim L, exampleReport->getDescription()); 3437239462Sdim BugReport::ranges_iterator Beg, End; 3438276479Sdim std::tie(Beg, End) = exampleReport->getRanges(); 3439234353Sdim for ( ; Beg != End; ++Beg) 3440234353Sdim piece->addRange(*Beg); 3441280031Sdim D->setEndOfPath(std::move(piece)); 3442218887Sdim } 3443218887Sdim 3444239462Sdim // Get the meta data. 3445239462Sdim const BugReport::ExtraTextList &Meta = exampleReport->getExtraText(); 3446239462Sdim for (BugReport::ExtraTextList::const_iterator i = Meta.begin(), 3447239462Sdim e = Meta.end(); i != e; ++i) { 3448239462Sdim D->addMeta(*i); 3449239462Sdim } 3450239462Sdim 3451280031Sdim PD.HandlePathDiagnostic(std::move(D)); 3452218887Sdim} 3453218887Sdim 3454234353Sdimvoid BugReporter::EmitBasicReport(const Decl *DeclWithIssue, 3455276479Sdim const CheckerBase *Checker, 3456276479Sdim StringRef Name, StringRef Category, 3457276479Sdim StringRef Str, PathDiagnosticLocation Loc, 3458276479Sdim ArrayRef<SourceRange> Ranges) { 3459276479Sdim EmitBasicReport(DeclWithIssue, Checker->getCheckName(), Name, Category, Str, 3460276479Sdim Loc, Ranges); 3461276479Sdim} 3462276479Sdimvoid BugReporter::EmitBasicReport(const Decl *DeclWithIssue, 3463276479Sdim CheckName CheckName, 3464276479Sdim StringRef name, StringRef category, 3465226633Sdim StringRef str, PathDiagnosticLocation Loc, 3466261991Sdim ArrayRef<SourceRange> Ranges) { 3467218887Sdim 3468219077Sdim // 'BT' is owned by BugReporter. 3469276479Sdim BugType *BT = getBugTypeForName(CheckName, name, category); 3470226633Sdim BugReport *R = new BugReport(*BT, str, Loc); 3471234353Sdim R->setDeclWithIssue(DeclWithIssue); 3472261991Sdim for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end(); 3473261991Sdim I != E; ++I) 3474261991Sdim R->addRange(*I); 3475243830Sdim emitReport(R); 3476218887Sdim} 3477219077Sdim 3478276479SdimBugType *BugReporter::getBugTypeForName(CheckName CheckName, StringRef name, 3479226633Sdim StringRef category) { 3480234353Sdim SmallString<136> fullDesc; 3481276479Sdim llvm::raw_svector_ostream(fullDesc) << CheckName.getName() << ":" << name 3482276479Sdim << ":" << category; 3483280031Sdim BugType *&BT = StrBugTypes[fullDesc]; 3484280031Sdim if (!BT) 3485276479Sdim BT = new BugType(CheckName, name, category); 3486219077Sdim return BT; 3487219077Sdim} 3488261991Sdim 3489276479SdimLLVM_DUMP_METHOD void PathPieces::dump() const { 3490261991Sdim unsigned index = 0; 3491261991Sdim for (PathPieces::const_iterator I = begin(), E = end(); I != E; ++I) { 3492261991Sdim llvm::errs() << "[" << index++ << "] "; 3493261991Sdim (*I)->dump(); 3494261991Sdim llvm::errs() << "\n"; 3495261991Sdim } 3496261991Sdim} 3497261991Sdim 3498261991Sdimvoid PathDiagnosticCallPiece::dump() const { 3499261991Sdim llvm::errs() << "CALL\n--------------\n"; 3500261991Sdim 3501261991Sdim if (const Stmt *SLoc = getLocStmt(getLocation())) 3502261991Sdim SLoc->dump(); 3503261991Sdim else if (const NamedDecl *ND = dyn_cast<NamedDecl>(getCallee())) 3504261991Sdim llvm::errs() << *ND << "\n"; 3505261991Sdim else 3506261991Sdim getLocation().dump(); 3507261991Sdim} 3508261991Sdim 3509261991Sdimvoid PathDiagnosticEventPiece::dump() const { 3510261991Sdim llvm::errs() << "EVENT\n--------------\n"; 3511261991Sdim llvm::errs() << getString() << "\n"; 3512261991Sdim llvm::errs() << " ---- at ----\n"; 3513261991Sdim getLocation().dump(); 3514261991Sdim} 3515261991Sdim 3516261991Sdimvoid PathDiagnosticControlFlowPiece::dump() const { 3517261991Sdim llvm::errs() << "CONTROL\n--------------\n"; 3518261991Sdim getStartLocation().dump(); 3519261991Sdim llvm::errs() << " ---- to ----\n"; 3520261991Sdim getEndLocation().dump(); 3521261991Sdim} 3522261991Sdim 3523261991Sdimvoid PathDiagnosticMacroPiece::dump() const { 3524261991Sdim llvm::errs() << "MACRO\n--------------\n"; 3525261991Sdim // FIXME: Print which macro is being invoked. 3526261991Sdim} 3527261991Sdim 3528261991Sdimvoid PathDiagnosticLocation::dump() const { 3529261991Sdim if (!isValid()) { 3530261991Sdim llvm::errs() << "<INVALID>\n"; 3531261991Sdim return; 3532261991Sdim } 3533261991Sdim 3534261991Sdim switch (K) { 3535261991Sdim case RangeK: 3536261991Sdim // FIXME: actually print the range. 3537261991Sdim llvm::errs() << "<range>\n"; 3538261991Sdim break; 3539261991Sdim case SingleLocK: 3540261991Sdim asLocation().dump(); 3541261991Sdim llvm::errs() << "\n"; 3542261991Sdim break; 3543261991Sdim case StmtK: 3544261991Sdim if (S) 3545261991Sdim S->dump(); 3546261991Sdim else 3547261991Sdim llvm::errs() << "<NULL STMT>\n"; 3548261991Sdim break; 3549261991Sdim case DeclK: 3550261991Sdim if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D)) 3551261991Sdim llvm::errs() << *ND << "\n"; 3552261991Sdim else if (isa<BlockDecl>(D)) 3553261991Sdim // FIXME: Make this nicer. 3554261991Sdim llvm::errs() << "<block>\n"; 3555261991Sdim else if (D) 3556261991Sdim llvm::errs() << "<unknown decl>\n"; 3557261991Sdim else 3558261991Sdim llvm::errs() << "<NULL DECL>\n"; 3559261991Sdim break; 3560261991Sdim } 3561261991Sdim} 3562