clang API Documentation
00001 // BugReporter.cpp - Generate PathDiagnostics for Bugs ------------*- C++ -*--// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines BugReporter, a utility class for generating 00011 // PathDiagnostics. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 00016 #include "clang/AST/ASTContext.h" 00017 #include "clang/AST/DeclObjC.h" 00018 #include "clang/AST/Expr.h" 00019 #include "clang/AST/ExprCXX.h" 00020 #include "clang/AST/ParentMap.h" 00021 #include "clang/AST/StmtCXX.h" 00022 #include "clang/AST/StmtObjC.h" 00023 #include "clang/Analysis/CFG.h" 00024 #include "clang/Analysis/ProgramPoint.h" 00025 #include "clang/Basic/SourceManager.h" 00026 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 00027 #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" 00028 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 00029 #include "llvm/ADT/DenseMap.h" 00030 #include "llvm/ADT/IntrusiveRefCntPtr.h" 00031 #include "llvm/ADT/STLExtras.h" 00032 #include "llvm/ADT/SmallString.h" 00033 #include "llvm/ADT/Statistic.h" 00034 #include "llvm/Support/raw_ostream.h" 00035 #include <memory> 00036 #include <queue> 00037 00038 using namespace clang; 00039 using namespace ento; 00040 00041 #define DEBUG_TYPE "BugReporter" 00042 00043 STATISTIC(MaxBugClassSize, 00044 "The maximum number of bug reports in the same equivalence class"); 00045 STATISTIC(MaxValidBugClassSize, 00046 "The maximum number of bug reports in the same equivalence class " 00047 "where at least one report is valid (not suppressed)"); 00048 00049 BugReporterVisitor::~BugReporterVisitor() {} 00050 00051 void BugReporterContext::anchor() {} 00052 00053 //===----------------------------------------------------------------------===// 00054 // Helper routines for walking the ExplodedGraph and fetching statements. 00055 //===----------------------------------------------------------------------===// 00056 00057 static const Stmt *GetPreviousStmt(const ExplodedNode *N) { 00058 for (N = N->getFirstPred(); N; N = N->getFirstPred()) 00059 if (const Stmt *S = PathDiagnosticLocation::getStmt(N)) 00060 return S; 00061 00062 return nullptr; 00063 } 00064 00065 static inline const Stmt* 00066 GetCurrentOrPreviousStmt(const ExplodedNode *N) { 00067 if (const Stmt *S = PathDiagnosticLocation::getStmt(N)) 00068 return S; 00069 00070 return GetPreviousStmt(N); 00071 } 00072 00073 //===----------------------------------------------------------------------===// 00074 // Diagnostic cleanup. 00075 //===----------------------------------------------------------------------===// 00076 00077 static PathDiagnosticEventPiece * 00078 eventsDescribeSameCondition(PathDiagnosticEventPiece *X, 00079 PathDiagnosticEventPiece *Y) { 00080 // Prefer diagnostics that come from ConditionBRVisitor over 00081 // those that came from TrackConstraintBRVisitor. 00082 const void *tagPreferred = ConditionBRVisitor::getTag(); 00083 const void *tagLesser = TrackConstraintBRVisitor::getTag(); 00084 00085 if (X->getLocation() != Y->getLocation()) 00086 return nullptr; 00087 00088 if (X->getTag() == tagPreferred && Y->getTag() == tagLesser) 00089 return X; 00090 00091 if (Y->getTag() == tagPreferred && X->getTag() == tagLesser) 00092 return Y; 00093 00094 return nullptr; 00095 } 00096 00097 /// An optimization pass over PathPieces that removes redundant diagnostics 00098 /// generated by both ConditionBRVisitor and TrackConstraintBRVisitor. Both 00099 /// BugReporterVisitors use different methods to generate diagnostics, with 00100 /// one capable of emitting diagnostics in some cases but not in others. This 00101 /// can lead to redundant diagnostic pieces at the same point in a path. 00102 static void removeRedundantMsgs(PathPieces &path) { 00103 unsigned N = path.size(); 00104 if (N < 2) 00105 return; 00106 // NOTE: this loop intentionally is not using an iterator. Instead, we 00107 // are streaming the path and modifying it in place. This is done by 00108 // grabbing the front, processing it, and if we decide to keep it append 00109 // it to the end of the path. The entire path is processed in this way. 00110 for (unsigned i = 0; i < N; ++i) { 00111 IntrusiveRefCntPtr<PathDiagnosticPiece> piece(path.front()); 00112 path.pop_front(); 00113 00114 switch (piece->getKind()) { 00115 case clang::ento::PathDiagnosticPiece::Call: 00116 removeRedundantMsgs(cast<PathDiagnosticCallPiece>(piece)->path); 00117 break; 00118 case clang::ento::PathDiagnosticPiece::Macro: 00119 removeRedundantMsgs(cast<PathDiagnosticMacroPiece>(piece)->subPieces); 00120 break; 00121 case clang::ento::PathDiagnosticPiece::ControlFlow: 00122 break; 00123 case clang::ento::PathDiagnosticPiece::Event: { 00124 if (i == N-1) 00125 break; 00126 00127 if (PathDiagnosticEventPiece *nextEvent = 00128 dyn_cast<PathDiagnosticEventPiece>(path.front().get())) { 00129 PathDiagnosticEventPiece *event = 00130 cast<PathDiagnosticEventPiece>(piece); 00131 // Check to see if we should keep one of the two pieces. If we 00132 // come up with a preference, record which piece to keep, and consume 00133 // another piece from the path. 00134 if (PathDiagnosticEventPiece *pieceToKeep = 00135 eventsDescribeSameCondition(event, nextEvent)) { 00136 piece = pieceToKeep; 00137 path.pop_front(); 00138 ++i; 00139 } 00140 } 00141 break; 00142 } 00143 } 00144 path.push_back(piece); 00145 } 00146 } 00147 00148 /// A map from PathDiagnosticPiece to the LocationContext of the inlined 00149 /// function call it represents. 00150 typedef llvm::DenseMap<const PathPieces *, const LocationContext *> 00151 LocationContextMap; 00152 00153 /// Recursively scan through a path and prune out calls and macros pieces 00154 /// that aren't needed. Return true if afterwards the path contains 00155 /// "interesting stuff" which means it shouldn't be pruned from the parent path. 00156 static bool removeUnneededCalls(PathPieces &pieces, BugReport *R, 00157 LocationContextMap &LCM) { 00158 bool containsSomethingInteresting = false; 00159 const unsigned N = pieces.size(); 00160 00161 for (unsigned i = 0 ; i < N ; ++i) { 00162 // Remove the front piece from the path. If it is still something we 00163 // want to keep once we are done, we will push it back on the end. 00164 IntrusiveRefCntPtr<PathDiagnosticPiece> piece(pieces.front()); 00165 pieces.pop_front(); 00166 00167 switch (piece->getKind()) { 00168 case PathDiagnosticPiece::Call: { 00169 PathDiagnosticCallPiece *call = cast<PathDiagnosticCallPiece>(piece); 00170 // Check if the location context is interesting. 00171 assert(LCM.count(&call->path)); 00172 if (R->isInteresting(LCM[&call->path])) { 00173 containsSomethingInteresting = true; 00174 break; 00175 } 00176 00177 if (!removeUnneededCalls(call->path, R, LCM)) 00178 continue; 00179 00180 containsSomethingInteresting = true; 00181 break; 00182 } 00183 case PathDiagnosticPiece::Macro: { 00184 PathDiagnosticMacroPiece *macro = cast<PathDiagnosticMacroPiece>(piece); 00185 if (!removeUnneededCalls(macro->subPieces, R, LCM)) 00186 continue; 00187 containsSomethingInteresting = true; 00188 break; 00189 } 00190 case PathDiagnosticPiece::Event: { 00191 PathDiagnosticEventPiece *event = cast<PathDiagnosticEventPiece>(piece); 00192 00193 // We never throw away an event, but we do throw it away wholesale 00194 // as part of a path if we throw the entire path away. 00195 containsSomethingInteresting |= !event->isPrunable(); 00196 break; 00197 } 00198 case PathDiagnosticPiece::ControlFlow: 00199 break; 00200 } 00201 00202 pieces.push_back(piece); 00203 } 00204 00205 return containsSomethingInteresting; 00206 } 00207 00208 /// Returns true if the given decl has been implicitly given a body, either by 00209 /// the analyzer or by the compiler proper. 00210 static bool hasImplicitBody(const Decl *D) { 00211 assert(D); 00212 return D->isImplicit() || !D->hasBody(); 00213 } 00214 00215 /// Recursively scan through a path and make sure that all call pieces have 00216 /// valid locations. 00217 static void 00218 adjustCallLocations(PathPieces &Pieces, 00219 PathDiagnosticLocation *LastCallLocation = nullptr) { 00220 for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E; ++I) { 00221 PathDiagnosticCallPiece *Call = dyn_cast<PathDiagnosticCallPiece>(*I); 00222 00223 if (!Call) { 00224 assert((*I)->getLocation().asLocation().isValid()); 00225 continue; 00226 } 00227 00228 if (LastCallLocation) { 00229 bool CallerIsImplicit = hasImplicitBody(Call->getCaller()); 00230 if (CallerIsImplicit || !Call->callEnter.asLocation().isValid()) 00231 Call->callEnter = *LastCallLocation; 00232 if (CallerIsImplicit || !Call->callReturn.asLocation().isValid()) 00233 Call->callReturn = *LastCallLocation; 00234 } 00235 00236 // Recursively clean out the subclass. Keep this call around if 00237 // it contains any informative diagnostics. 00238 PathDiagnosticLocation *ThisCallLocation; 00239 if (Call->callEnterWithin.asLocation().isValid() && 00240 !hasImplicitBody(Call->getCallee())) 00241 ThisCallLocation = &Call->callEnterWithin; 00242 else 00243 ThisCallLocation = &Call->callEnter; 00244 00245 assert(ThisCallLocation && "Outermost call has an invalid location"); 00246 adjustCallLocations(Call->path, ThisCallLocation); 00247 } 00248 } 00249 00250 /// Remove edges in and out of C++ default initializer expressions. These are 00251 /// for fields that have in-class initializers, as opposed to being initialized 00252 /// explicitly in a constructor or braced list. 00253 static void removeEdgesToDefaultInitializers(PathPieces &Pieces) { 00254 for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) { 00255 if (PathDiagnosticCallPiece *C = dyn_cast<PathDiagnosticCallPiece>(*I)) 00256 removeEdgesToDefaultInitializers(C->path); 00257 00258 if (PathDiagnosticMacroPiece *M = dyn_cast<PathDiagnosticMacroPiece>(*I)) 00259 removeEdgesToDefaultInitializers(M->subPieces); 00260 00261 if (PathDiagnosticControlFlowPiece *CF = 00262 dyn_cast<PathDiagnosticControlFlowPiece>(*I)) { 00263 const Stmt *Start = CF->getStartLocation().asStmt(); 00264 const Stmt *End = CF->getEndLocation().asStmt(); 00265 if (Start && isa<CXXDefaultInitExpr>(Start)) { 00266 I = Pieces.erase(I); 00267 continue; 00268 } else if (End && isa<CXXDefaultInitExpr>(End)) { 00269 PathPieces::iterator Next = std::next(I); 00270 if (Next != E) { 00271 if (PathDiagnosticControlFlowPiece *NextCF = 00272 dyn_cast<PathDiagnosticControlFlowPiece>(*Next)) { 00273 NextCF->setStartLocation(CF->getStartLocation()); 00274 } 00275 } 00276 I = Pieces.erase(I); 00277 continue; 00278 } 00279 } 00280 00281 I++; 00282 } 00283 } 00284 00285 /// Remove all pieces with invalid locations as these cannot be serialized. 00286 /// We might have pieces with invalid locations as a result of inlining Body 00287 /// Farm generated functions. 00288 static void removePiecesWithInvalidLocations(PathPieces &Pieces) { 00289 for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) { 00290 if (PathDiagnosticCallPiece *C = dyn_cast<PathDiagnosticCallPiece>(*I)) 00291 removePiecesWithInvalidLocations(C->path); 00292 00293 if (PathDiagnosticMacroPiece *M = dyn_cast<PathDiagnosticMacroPiece>(*I)) 00294 removePiecesWithInvalidLocations(M->subPieces); 00295 00296 if (!(*I)->getLocation().isValid() || 00297 !(*I)->getLocation().asLocation().isValid()) { 00298 I = Pieces.erase(I); 00299 continue; 00300 } 00301 I++; 00302 } 00303 } 00304 00305 //===----------------------------------------------------------------------===// 00306 // PathDiagnosticBuilder and its associated routines and helper objects. 00307 //===----------------------------------------------------------------------===// 00308 00309 namespace { 00310 class NodeMapClosure : public BugReport::NodeResolver { 00311 InterExplodedGraphMap &M; 00312 public: 00313 NodeMapClosure(InterExplodedGraphMap &m) : M(m) {} 00314 00315 const ExplodedNode *getOriginalNode(const ExplodedNode *N) override { 00316 return M.lookup(N); 00317 } 00318 }; 00319 00320 class PathDiagnosticBuilder : public BugReporterContext { 00321 BugReport *R; 00322 PathDiagnosticConsumer *PDC; 00323 NodeMapClosure NMC; 00324 public: 00325 const LocationContext *LC; 00326 00327 PathDiagnosticBuilder(GRBugReporter &br, 00328 BugReport *r, InterExplodedGraphMap &Backmap, 00329 PathDiagnosticConsumer *pdc) 00330 : BugReporterContext(br), 00331 R(r), PDC(pdc), NMC(Backmap), LC(r->getErrorNode()->getLocationContext()) 00332 {} 00333 00334 PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N); 00335 00336 PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os, 00337 const ExplodedNode *N); 00338 00339 BugReport *getBugReport() { return R; } 00340 00341 Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); } 00342 00343 ParentMap& getParentMap() { return LC->getParentMap(); } 00344 00345 const Stmt *getParent(const Stmt *S) { 00346 return getParentMap().getParent(S); 00347 } 00348 00349 NodeMapClosure& getNodeResolver() override { return NMC; } 00350 00351 PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S); 00352 00353 PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const { 00354 return PDC ? PDC->getGenerationScheme() : PathDiagnosticConsumer::Extensive; 00355 } 00356 00357 bool supportsLogicalOpControlFlow() const { 00358 return PDC ? PDC->supportsLogicalOpControlFlow() : true; 00359 } 00360 }; 00361 } // end anonymous namespace 00362 00363 PathDiagnosticLocation 00364 PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) { 00365 if (const Stmt *S = PathDiagnosticLocation::getNextStmt(N)) 00366 return PathDiagnosticLocation(S, getSourceManager(), LC); 00367 00368 return PathDiagnosticLocation::createDeclEnd(N->getLocationContext(), 00369 getSourceManager()); 00370 } 00371 00372 PathDiagnosticLocation 00373 PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os, 00374 const ExplodedNode *N) { 00375 00376 // Slow, but probably doesn't matter. 00377 if (os.str().empty()) 00378 os << ' '; 00379 00380 const PathDiagnosticLocation &Loc = ExecutionContinues(N); 00381 00382 if (Loc.asStmt()) 00383 os << "Execution continues on line " 00384 << getSourceManager().getExpansionLineNumber(Loc.asLocation()) 00385 << '.'; 00386 else { 00387 os << "Execution jumps to the end of the "; 00388 const Decl *D = N->getLocationContext()->getDecl(); 00389 if (isa<ObjCMethodDecl>(D)) 00390 os << "method"; 00391 else if (isa<FunctionDecl>(D)) 00392 os << "function"; 00393 else { 00394 assert(isa<BlockDecl>(D)); 00395 os << "anonymous block"; 00396 } 00397 os << '.'; 00398 } 00399 00400 return Loc; 00401 } 00402 00403 static const Stmt *getEnclosingParent(const Stmt *S, const ParentMap &PM) { 00404 if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S))) 00405 return PM.getParentIgnoreParens(S); 00406 00407 const Stmt *Parent = PM.getParentIgnoreParens(S); 00408 if (!Parent) 00409 return nullptr; 00410 00411 switch (Parent->getStmtClass()) { 00412 case Stmt::ForStmtClass: 00413 case Stmt::DoStmtClass: 00414 case Stmt::WhileStmtClass: 00415 case Stmt::ObjCForCollectionStmtClass: 00416 case Stmt::CXXForRangeStmtClass: 00417 return Parent; 00418 default: 00419 break; 00420 } 00421 00422 return nullptr; 00423 } 00424 00425 static PathDiagnosticLocation 00426 getEnclosingStmtLocation(const Stmt *S, SourceManager &SMgr, const ParentMap &P, 00427 const LocationContext *LC, bool allowNestedContexts) { 00428 if (!S) 00429 return PathDiagnosticLocation(); 00430 00431 while (const Stmt *Parent = getEnclosingParent(S, P)) { 00432 switch (Parent->getStmtClass()) { 00433 case Stmt::BinaryOperatorClass: { 00434 const BinaryOperator *B = cast<BinaryOperator>(Parent); 00435 if (B->isLogicalOp()) 00436 return PathDiagnosticLocation(allowNestedContexts ? B : S, SMgr, LC); 00437 break; 00438 } 00439 case Stmt::CompoundStmtClass: 00440 case Stmt::StmtExprClass: 00441 return PathDiagnosticLocation(S, SMgr, LC); 00442 case Stmt::ChooseExprClass: 00443 // Similar to '?' if we are referring to condition, just have the edge 00444 // point to the entire choose expression. 00445 if (allowNestedContexts || cast<ChooseExpr>(Parent)->getCond() == S) 00446 return PathDiagnosticLocation(Parent, SMgr, LC); 00447 else 00448 return PathDiagnosticLocation(S, SMgr, LC); 00449 case Stmt::BinaryConditionalOperatorClass: 00450 case Stmt::ConditionalOperatorClass: 00451 // For '?', if we are referring to condition, just have the edge point 00452 // to the entire '?' expression. 00453 if (allowNestedContexts || 00454 cast<AbstractConditionalOperator>(Parent)->getCond() == S) 00455 return PathDiagnosticLocation(Parent, SMgr, LC); 00456 else 00457 return PathDiagnosticLocation(S, SMgr, LC); 00458 case Stmt::CXXForRangeStmtClass: 00459 if (cast<CXXForRangeStmt>(Parent)->getBody() == S) 00460 return PathDiagnosticLocation(S, SMgr, LC); 00461 break; 00462 case Stmt::DoStmtClass: 00463 return PathDiagnosticLocation(S, SMgr, LC); 00464 case Stmt::ForStmtClass: 00465 if (cast<ForStmt>(Parent)->getBody() == S) 00466 return PathDiagnosticLocation(S, SMgr, LC); 00467 break; 00468 case Stmt::IfStmtClass: 00469 if (cast<IfStmt>(Parent)->getCond() != S) 00470 return PathDiagnosticLocation(S, SMgr, LC); 00471 break; 00472 case Stmt::ObjCForCollectionStmtClass: 00473 if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S) 00474 return PathDiagnosticLocation(S, SMgr, LC); 00475 break; 00476 case Stmt::WhileStmtClass: 00477 if (cast<WhileStmt>(Parent)->getCond() != S) 00478 return PathDiagnosticLocation(S, SMgr, LC); 00479 break; 00480 default: 00481 break; 00482 } 00483 00484 S = Parent; 00485 } 00486 00487 assert(S && "Cannot have null Stmt for PathDiagnosticLocation"); 00488 00489 return PathDiagnosticLocation(S, SMgr, LC); 00490 } 00491 00492 PathDiagnosticLocation 00493 PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { 00494 assert(S && "Null Stmt passed to getEnclosingStmtLocation"); 00495 return ::getEnclosingStmtLocation(S, getSourceManager(), getParentMap(), LC, 00496 /*allowNestedContexts=*/false); 00497 } 00498 00499 //===----------------------------------------------------------------------===// 00500 // "Visitors only" path diagnostic generation algorithm. 00501 //===----------------------------------------------------------------------===// 00502 static bool GenerateVisitorsOnlyPathDiagnostic( 00503 PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, 00504 ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors) { 00505 // All path generation skips the very first node (the error node). 00506 // This is because there is special handling for the end-of-path note. 00507 N = N->getFirstPred(); 00508 if (!N) 00509 return true; 00510 00511 BugReport *R = PDB.getBugReport(); 00512 while (const ExplodedNode *Pred = N->getFirstPred()) { 00513 for (auto &V : visitors) { 00514 // Visit all the node pairs, but throw the path pieces away. 00515 PathDiagnosticPiece *Piece = V->VisitNode(N, Pred, PDB, *R); 00516 delete Piece; 00517 } 00518 00519 N = Pred; 00520 } 00521 00522 return R->isValid(); 00523 } 00524 00525 //===----------------------------------------------------------------------===// 00526 // "Minimal" path diagnostic generation algorithm. 00527 //===----------------------------------------------------------------------===// 00528 typedef std::pair<PathDiagnosticCallPiece*, const ExplodedNode*> StackDiagPair; 00529 typedef SmallVector<StackDiagPair, 6> StackDiagVector; 00530 00531 static void updateStackPiecesWithMessage(PathDiagnosticPiece *P, 00532 StackDiagVector &CallStack) { 00533 // If the piece contains a special message, add it to all the call 00534 // pieces on the active stack. 00535 if (PathDiagnosticEventPiece *ep = 00536 dyn_cast<PathDiagnosticEventPiece>(P)) { 00537 00538 if (ep->hasCallStackHint()) 00539 for (StackDiagVector::iterator I = CallStack.begin(), 00540 E = CallStack.end(); I != E; ++I) { 00541 PathDiagnosticCallPiece *CP = I->first; 00542 const ExplodedNode *N = I->second; 00543 std::string stackMsg = ep->getCallStackMessage(N); 00544 00545 // The last message on the path to final bug is the most important 00546 // one. Since we traverse the path backwards, do not add the message 00547 // if one has been previously added. 00548 if (!CP->hasCallStackMessage()) 00549 CP->setCallStackMessage(stackMsg); 00550 } 00551 } 00552 } 00553 00554 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM); 00555 00556 static bool GenerateMinimalPathDiagnostic( 00557 PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, 00558 LocationContextMap &LCM, 00559 ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors) { 00560 00561 SourceManager& SMgr = PDB.getSourceManager(); 00562 const LocationContext *LC = PDB.LC; 00563 const ExplodedNode *NextNode = N->pred_empty() 00564 ? nullptr : *(N->pred_begin()); 00565 00566 StackDiagVector CallStack; 00567 00568 while (NextNode) { 00569 N = NextNode; 00570 PDB.LC = N->getLocationContext(); 00571 NextNode = N->getFirstPred(); 00572 00573 ProgramPoint P = N->getLocation(); 00574 00575 do { 00576 if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) { 00577 PathDiagnosticCallPiece *C = 00578 PathDiagnosticCallPiece::construct(N, *CE, SMgr); 00579 // Record the mapping from call piece to LocationContext. 00580 LCM[&C->path] = CE->getCalleeContext(); 00581 PD.getActivePath().push_front(C); 00582 PD.pushActivePath(&C->path); 00583 CallStack.push_back(StackDiagPair(C, N)); 00584 break; 00585 } 00586 00587 if (Optional<CallEnter> CE = P.getAs<CallEnter>()) { 00588 // Flush all locations, and pop the active path. 00589 bool VisitedEntireCall = PD.isWithinCall(); 00590 PD.popActivePath(); 00591 00592 // Either we just added a bunch of stuff to the top-level path, or 00593 // we have a previous CallExitEnd. If the former, it means that the 00594 // path terminated within a function call. We must then take the 00595 // current contents of the active path and place it within 00596 // a new PathDiagnosticCallPiece. 00597 PathDiagnosticCallPiece *C; 00598 if (VisitedEntireCall) { 00599 C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); 00600 } else { 00601 const Decl *Caller = CE->getLocationContext()->getDecl(); 00602 C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 00603 // Record the mapping from call piece to LocationContext. 00604 LCM[&C->path] = CE->getCalleeContext(); 00605 } 00606 00607 C->setCallee(*CE, SMgr); 00608 if (!CallStack.empty()) { 00609 assert(CallStack.back().first == C); 00610 CallStack.pop_back(); 00611 } 00612 break; 00613 } 00614 00615 if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) { 00616 const CFGBlock *Src = BE->getSrc(); 00617 const CFGBlock *Dst = BE->getDst(); 00618 const Stmt *T = Src->getTerminator(); 00619 00620 if (!T) 00621 break; 00622 00623 PathDiagnosticLocation Start = 00624 PathDiagnosticLocation::createBegin(T, SMgr, 00625 N->getLocationContext()); 00626 00627 switch (T->getStmtClass()) { 00628 default: 00629 break; 00630 00631 case Stmt::GotoStmtClass: 00632 case Stmt::IndirectGotoStmtClass: { 00633 const Stmt *S = PathDiagnosticLocation::getNextStmt(N); 00634 00635 if (!S) 00636 break; 00637 00638 std::string sbuf; 00639 llvm::raw_string_ostream os(sbuf); 00640 const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S); 00641 00642 os << "Control jumps to line " 00643 << End.asLocation().getExpansionLineNumber(); 00644 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00645 Start, End, os.str())); 00646 break; 00647 } 00648 00649 case Stmt::SwitchStmtClass: { 00650 // Figure out what case arm we took. 00651 std::string sbuf; 00652 llvm::raw_string_ostream os(sbuf); 00653 00654 if (const Stmt *S = Dst->getLabel()) { 00655 PathDiagnosticLocation End(S, SMgr, LC); 00656 00657 switch (S->getStmtClass()) { 00658 default: 00659 os << "No cases match in the switch statement. " 00660 "Control jumps to line " 00661 << End.asLocation().getExpansionLineNumber(); 00662 break; 00663 case Stmt::DefaultStmtClass: 00664 os << "Control jumps to the 'default' case at line " 00665 << End.asLocation().getExpansionLineNumber(); 00666 break; 00667 00668 case Stmt::CaseStmtClass: { 00669 os << "Control jumps to 'case "; 00670 const CaseStmt *Case = cast<CaseStmt>(S); 00671 const Expr *LHS = Case->getLHS()->IgnoreParenCasts(); 00672 00673 // Determine if it is an enum. 00674 bool GetRawInt = true; 00675 00676 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) { 00677 // FIXME: Maybe this should be an assertion. Are there cases 00678 // were it is not an EnumConstantDecl? 00679 const EnumConstantDecl *D = 00680 dyn_cast<EnumConstantDecl>(DR->getDecl()); 00681 00682 if (D) { 00683 GetRawInt = false; 00684 os << *D; 00685 } 00686 } 00687 00688 if (GetRawInt) 00689 os << LHS->EvaluateKnownConstInt(PDB.getASTContext()); 00690 00691 os << ":' at line " 00692 << End.asLocation().getExpansionLineNumber(); 00693 break; 00694 } 00695 } 00696 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00697 Start, End, os.str())); 00698 } 00699 else { 00700 os << "'Default' branch taken. "; 00701 const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N); 00702 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00703 Start, End, os.str())); 00704 } 00705 00706 break; 00707 } 00708 00709 case Stmt::BreakStmtClass: 00710 case Stmt::ContinueStmtClass: { 00711 std::string sbuf; 00712 llvm::raw_string_ostream os(sbuf); 00713 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 00714 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00715 Start, End, os.str())); 00716 break; 00717 } 00718 00719 // Determine control-flow for ternary '?'. 00720 case Stmt::BinaryConditionalOperatorClass: 00721 case Stmt::ConditionalOperatorClass: { 00722 std::string sbuf; 00723 llvm::raw_string_ostream os(sbuf); 00724 os << "'?' condition is "; 00725 00726 if (*(Src->succ_begin()+1) == Dst) 00727 os << "false"; 00728 else 00729 os << "true"; 00730 00731 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 00732 00733 if (const Stmt *S = End.asStmt()) 00734 End = PDB.getEnclosingStmtLocation(S); 00735 00736 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00737 Start, End, os.str())); 00738 break; 00739 } 00740 00741 // Determine control-flow for short-circuited '&&' and '||'. 00742 case Stmt::BinaryOperatorClass: { 00743 if (!PDB.supportsLogicalOpControlFlow()) 00744 break; 00745 00746 const BinaryOperator *B = cast<BinaryOperator>(T); 00747 std::string sbuf; 00748 llvm::raw_string_ostream os(sbuf); 00749 os << "Left side of '"; 00750 00751 if (B->getOpcode() == BO_LAnd) { 00752 os << "&&" << "' is "; 00753 00754 if (*(Src->succ_begin()+1) == Dst) { 00755 os << "false"; 00756 PathDiagnosticLocation End(B->getLHS(), SMgr, LC); 00757 PathDiagnosticLocation Start = 00758 PathDiagnosticLocation::createOperatorLoc(B, SMgr); 00759 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00760 Start, End, os.str())); 00761 } 00762 else { 00763 os << "true"; 00764 PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); 00765 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 00766 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00767 Start, End, os.str())); 00768 } 00769 } 00770 else { 00771 assert(B->getOpcode() == BO_LOr); 00772 os << "||" << "' is "; 00773 00774 if (*(Src->succ_begin()+1) == Dst) { 00775 os << "false"; 00776 PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); 00777 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 00778 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00779 Start, End, os.str())); 00780 } 00781 else { 00782 os << "true"; 00783 PathDiagnosticLocation End(B->getLHS(), SMgr, LC); 00784 PathDiagnosticLocation Start = 00785 PathDiagnosticLocation::createOperatorLoc(B, SMgr); 00786 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00787 Start, End, os.str())); 00788 } 00789 } 00790 00791 break; 00792 } 00793 00794 case Stmt::DoStmtClass: { 00795 if (*(Src->succ_begin()) == Dst) { 00796 std::string sbuf; 00797 llvm::raw_string_ostream os(sbuf); 00798 00799 os << "Loop condition is true. "; 00800 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 00801 00802 if (const Stmt *S = End.asStmt()) 00803 End = PDB.getEnclosingStmtLocation(S); 00804 00805 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00806 Start, End, os.str())); 00807 } 00808 else { 00809 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 00810 00811 if (const Stmt *S = End.asStmt()) 00812 End = PDB.getEnclosingStmtLocation(S); 00813 00814 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00815 Start, End, "Loop condition is false. Exiting loop")); 00816 } 00817 00818 break; 00819 } 00820 00821 case Stmt::WhileStmtClass: 00822 case Stmt::ForStmtClass: { 00823 if (*(Src->succ_begin()+1) == Dst) { 00824 std::string sbuf; 00825 llvm::raw_string_ostream os(sbuf); 00826 00827 os << "Loop condition is false. "; 00828 PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); 00829 if (const Stmt *S = End.asStmt()) 00830 End = PDB.getEnclosingStmtLocation(S); 00831 00832 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00833 Start, End, os.str())); 00834 } 00835 else { 00836 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 00837 if (const Stmt *S = End.asStmt()) 00838 End = PDB.getEnclosingStmtLocation(S); 00839 00840 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00841 Start, End, "Loop condition is true. Entering loop body")); 00842 } 00843 00844 break; 00845 } 00846 00847 case Stmt::IfStmtClass: { 00848 PathDiagnosticLocation End = PDB.ExecutionContinues(N); 00849 00850 if (const Stmt *S = End.asStmt()) 00851 End = PDB.getEnclosingStmtLocation(S); 00852 00853 if (*(Src->succ_begin()+1) == Dst) 00854 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00855 Start, End, "Taking false branch")); 00856 else 00857 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( 00858 Start, End, "Taking true branch")); 00859 00860 break; 00861 } 00862 } 00863 } 00864 } while(0); 00865 00866 if (NextNode) { 00867 // Add diagnostic pieces from custom visitors. 00868 BugReport *R = PDB.getBugReport(); 00869 for (auto &V : visitors) { 00870 if (PathDiagnosticPiece *p = V->VisitNode(N, NextNode, PDB, *R)) { 00871 PD.getActivePath().push_front(p); 00872 updateStackPiecesWithMessage(p, CallStack); 00873 } 00874 } 00875 } 00876 } 00877 00878 if (!PDB.getBugReport()->isValid()) 00879 return false; 00880 00881 // After constructing the full PathDiagnostic, do a pass over it to compact 00882 // PathDiagnosticPieces that occur within a macro. 00883 CompactPathDiagnostic(PD.getMutablePieces(), PDB.getSourceManager()); 00884 return true; 00885 } 00886 00887 //===----------------------------------------------------------------------===// 00888 // "Extensive" PathDiagnostic generation. 00889 //===----------------------------------------------------------------------===// 00890 00891 static bool IsControlFlowExpr(const Stmt *S) { 00892 const Expr *E = dyn_cast<Expr>(S); 00893 00894 if (!E) 00895 return false; 00896 00897 E = E->IgnoreParenCasts(); 00898 00899 if (isa<AbstractConditionalOperator>(E)) 00900 return true; 00901 00902 if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E)) 00903 if (B->isLogicalOp()) 00904 return true; 00905 00906 return false; 00907 } 00908 00909 namespace { 00910 class ContextLocation : public PathDiagnosticLocation { 00911 bool IsDead; 00912 public: 00913 ContextLocation(const PathDiagnosticLocation &L, bool isdead = false) 00914 : PathDiagnosticLocation(L), IsDead(isdead) {} 00915 00916 void markDead() { IsDead = true; } 00917 bool isDead() const { return IsDead; } 00918 }; 00919 00920 static PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L, 00921 const LocationContext *LC, 00922 bool firstCharOnly = false) { 00923 if (const Stmt *S = L.asStmt()) { 00924 const Stmt *Original = S; 00925 while (1) { 00926 // Adjust the location for some expressions that are best referenced 00927 // by one of their subexpressions. 00928 switch (S->getStmtClass()) { 00929 default: 00930 break; 00931 case Stmt::ParenExprClass: 00932 case Stmt::GenericSelectionExprClass: 00933 S = cast<Expr>(S)->IgnoreParens(); 00934 firstCharOnly = true; 00935 continue; 00936 case Stmt::BinaryConditionalOperatorClass: 00937 case Stmt::ConditionalOperatorClass: 00938 S = cast<AbstractConditionalOperator>(S)->getCond(); 00939 firstCharOnly = true; 00940 continue; 00941 case Stmt::ChooseExprClass: 00942 S = cast<ChooseExpr>(S)->getCond(); 00943 firstCharOnly = true; 00944 continue; 00945 case Stmt::BinaryOperatorClass: 00946 S = cast<BinaryOperator>(S)->getLHS(); 00947 firstCharOnly = true; 00948 continue; 00949 } 00950 00951 break; 00952 } 00953 00954 if (S != Original) 00955 L = PathDiagnosticLocation(S, L.getManager(), LC); 00956 } 00957 00958 if (firstCharOnly) 00959 L = PathDiagnosticLocation::createSingleLocation(L); 00960 00961 return L; 00962 } 00963 00964 class EdgeBuilder { 00965 std::vector<ContextLocation> CLocs; 00966 typedef std::vector<ContextLocation>::iterator iterator; 00967 PathDiagnostic &PD; 00968 PathDiagnosticBuilder &PDB; 00969 PathDiagnosticLocation PrevLoc; 00970 00971 bool IsConsumedExpr(const PathDiagnosticLocation &L); 00972 00973 bool containsLocation(const PathDiagnosticLocation &Container, 00974 const PathDiagnosticLocation &Containee); 00975 00976 PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L); 00977 00978 00979 00980 void popLocation() { 00981 if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) { 00982 // For contexts, we only one the first character as the range. 00983 rawAddEdge(cleanUpLocation(CLocs.back(), PDB.LC, true)); 00984 } 00985 CLocs.pop_back(); 00986 } 00987 00988 public: 00989 EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb) 00990 : PD(pd), PDB(pdb) { 00991 00992 // If the PathDiagnostic already has pieces, add the enclosing statement 00993 // of the first piece as a context as well. 00994 if (!PD.path.empty()) { 00995 PrevLoc = (*PD.path.begin())->getLocation(); 00996 00997 if (const Stmt *S = PrevLoc.asStmt()) 00998 addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 00999 } 01000 } 01001 01002 ~EdgeBuilder() { 01003 while (!CLocs.empty()) popLocation(); 01004 01005 // Finally, add an initial edge from the start location of the first 01006 // statement (if it doesn't already exist). 01007 PathDiagnosticLocation L = PathDiagnosticLocation::createDeclBegin( 01008 PDB.LC, 01009 PDB.getSourceManager()); 01010 if (L.isValid()) 01011 rawAddEdge(L); 01012 } 01013 01014 void flushLocations() { 01015 while (!CLocs.empty()) 01016 popLocation(); 01017 PrevLoc = PathDiagnosticLocation(); 01018 } 01019 01020 void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false, 01021 bool IsPostJump = false); 01022 01023 void rawAddEdge(PathDiagnosticLocation NewLoc); 01024 01025 void addContext(const Stmt *S); 01026 void addContext(const PathDiagnosticLocation &L); 01027 void addExtendedContext(const Stmt *S); 01028 }; 01029 } // end anonymous namespace 01030 01031 01032 PathDiagnosticLocation 01033 EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) { 01034 if (const Stmt *S = L.asStmt()) { 01035 if (IsControlFlowExpr(S)) 01036 return L; 01037 01038 return PDB.getEnclosingStmtLocation(S); 01039 } 01040 01041 return L; 01042 } 01043 01044 bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container, 01045 const PathDiagnosticLocation &Containee) { 01046 01047 if (Container == Containee) 01048 return true; 01049 01050 if (Container.asDecl()) 01051 return true; 01052 01053 if (const Stmt *S = Containee.asStmt()) 01054 if (const Stmt *ContainerS = Container.asStmt()) { 01055 while (S) { 01056 if (S == ContainerS) 01057 return true; 01058 S = PDB.getParent(S); 01059 } 01060 return false; 01061 } 01062 01063 // Less accurate: compare using source ranges. 01064 SourceRange ContainerR = Container.asRange(); 01065 SourceRange ContaineeR = Containee.asRange(); 01066 01067 SourceManager &SM = PDB.getSourceManager(); 01068 SourceLocation ContainerRBeg = SM.getExpansionLoc(ContainerR.getBegin()); 01069 SourceLocation ContainerREnd = SM.getExpansionLoc(ContainerR.getEnd()); 01070 SourceLocation ContaineeRBeg = SM.getExpansionLoc(ContaineeR.getBegin()); 01071 SourceLocation ContaineeREnd = SM.getExpansionLoc(ContaineeR.getEnd()); 01072 01073 unsigned ContainerBegLine = SM.getExpansionLineNumber(ContainerRBeg); 01074 unsigned ContainerEndLine = SM.getExpansionLineNumber(ContainerREnd); 01075 unsigned ContaineeBegLine = SM.getExpansionLineNumber(ContaineeRBeg); 01076 unsigned ContaineeEndLine = SM.getExpansionLineNumber(ContaineeREnd); 01077 01078 assert(ContainerBegLine <= ContainerEndLine); 01079 assert(ContaineeBegLine <= ContaineeEndLine); 01080 01081 return (ContainerBegLine <= ContaineeBegLine && 01082 ContainerEndLine >= ContaineeEndLine && 01083 (ContainerBegLine != ContaineeBegLine || 01084 SM.getExpansionColumnNumber(ContainerRBeg) <= 01085 SM.getExpansionColumnNumber(ContaineeRBeg)) && 01086 (ContainerEndLine != ContaineeEndLine || 01087 SM.getExpansionColumnNumber(ContainerREnd) >= 01088 SM.getExpansionColumnNumber(ContaineeREnd))); 01089 } 01090 01091 void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) { 01092 if (!PrevLoc.isValid()) { 01093 PrevLoc = NewLoc; 01094 return; 01095 } 01096 01097 const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc, PDB.LC); 01098 const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc, PDB.LC); 01099 01100 if (PrevLocClean.asLocation().isInvalid()) { 01101 PrevLoc = NewLoc; 01102 return; 01103 } 01104 01105 if (NewLocClean.asLocation() == PrevLocClean.asLocation()) 01106 return; 01107 01108 // FIXME: Ignore intra-macro edges for now. 01109 if (NewLocClean.asLocation().getExpansionLoc() == 01110 PrevLocClean.asLocation().getExpansionLoc()) 01111 return; 01112 01113 PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean)); 01114 PrevLoc = NewLoc; 01115 } 01116 01117 void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd, 01118 bool IsPostJump) { 01119 01120 if (!alwaysAdd && NewLoc.asLocation().isMacroID()) 01121 return; 01122 01123 const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc); 01124 01125 while (!CLocs.empty()) { 01126 ContextLocation &TopContextLoc = CLocs.back(); 01127 01128 // Is the top location context the same as the one for the new location? 01129 if (TopContextLoc == CLoc) { 01130 if (alwaysAdd) { 01131 if (IsConsumedExpr(TopContextLoc)) 01132 TopContextLoc.markDead(); 01133 01134 rawAddEdge(NewLoc); 01135 } 01136 01137 if (IsPostJump) 01138 TopContextLoc.markDead(); 01139 return; 01140 } 01141 01142 if (containsLocation(TopContextLoc, CLoc)) { 01143 if (alwaysAdd) { 01144 rawAddEdge(NewLoc); 01145 01146 if (IsConsumedExpr(CLoc)) { 01147 CLocs.push_back(ContextLocation(CLoc, /*IsDead=*/true)); 01148 return; 01149 } 01150 } 01151 01152 CLocs.push_back(ContextLocation(CLoc, /*IsDead=*/IsPostJump)); 01153 return; 01154 } 01155 01156 // Context does not contain the location. Flush it. 01157 popLocation(); 01158 } 01159 01160 // If we reach here, there is no enclosing context. Just add the edge. 01161 rawAddEdge(NewLoc); 01162 } 01163 01164 bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) { 01165 if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt())) 01166 return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X); 01167 01168 return false; 01169 } 01170 01171 void EdgeBuilder::addExtendedContext(const Stmt *S) { 01172 if (!S) 01173 return; 01174 01175 const Stmt *Parent = PDB.getParent(S); 01176 while (Parent) { 01177 if (isa<CompoundStmt>(Parent)) 01178 Parent = PDB.getParent(Parent); 01179 else 01180 break; 01181 } 01182 01183 if (Parent) { 01184 switch (Parent->getStmtClass()) { 01185 case Stmt::DoStmtClass: 01186 case Stmt::ObjCAtSynchronizedStmtClass: 01187 addContext(Parent); 01188 default: 01189 break; 01190 } 01191 } 01192 01193 addContext(S); 01194 } 01195 01196 void EdgeBuilder::addContext(const Stmt *S) { 01197 if (!S) 01198 return; 01199 01200 PathDiagnosticLocation L(S, PDB.getSourceManager(), PDB.LC); 01201 addContext(L); 01202 } 01203 01204 void EdgeBuilder::addContext(const PathDiagnosticLocation &L) { 01205 while (!CLocs.empty()) { 01206 const PathDiagnosticLocation &TopContextLoc = CLocs.back(); 01207 01208 // Is the top location context the same as the one for the new location? 01209 if (TopContextLoc == L) 01210 return; 01211 01212 if (containsLocation(TopContextLoc, L)) { 01213 CLocs.push_back(L); 01214 return; 01215 } 01216 01217 // Context does not contain the location. Flush it. 01218 popLocation(); 01219 } 01220 01221 CLocs.push_back(L); 01222 } 01223 01224 // Cone-of-influence: support the reverse propagation of "interesting" symbols 01225 // and values by tracing interesting calculations backwards through evaluated 01226 // expressions along a path. This is probably overly complicated, but the idea 01227 // is that if an expression computed an "interesting" value, the child 01228 // expressions are are also likely to be "interesting" as well (which then 01229 // propagates to the values they in turn compute). This reverse propagation 01230 // is needed to track interesting correlations across function call boundaries, 01231 // where formal arguments bind to actual arguments, etc. This is also needed 01232 // because the constraint solver sometimes simplifies certain symbolic values 01233 // into constants when appropriate, and this complicates reasoning about 01234 // interesting values. 01235 typedef llvm::DenseSet<const Expr *> InterestingExprs; 01236 01237 static void reversePropagateIntererstingSymbols(BugReport &R, 01238 InterestingExprs &IE, 01239 const ProgramState *State, 01240 const Expr *Ex, 01241 const LocationContext *LCtx) { 01242 SVal V = State->getSVal(Ex, LCtx); 01243 if (!(R.isInteresting(V) || IE.count(Ex))) 01244 return; 01245 01246 switch (Ex->getStmtClass()) { 01247 default: 01248 if (!isa<CastExpr>(Ex)) 01249 break; 01250 // Fall through. 01251 case Stmt::BinaryOperatorClass: 01252 case Stmt::UnaryOperatorClass: { 01253 for (Stmt::const_child_iterator CI = Ex->child_begin(), 01254 CE = Ex->child_end(); 01255 CI != CE; ++CI) { 01256 if (const Expr *child = dyn_cast_or_null<Expr>(*CI)) { 01257 IE.insert(child); 01258 SVal ChildV = State->getSVal(child, LCtx); 01259 R.markInteresting(ChildV); 01260 } 01261 } 01262 break; 01263 } 01264 } 01265 01266 R.markInteresting(V); 01267 } 01268 01269 static void reversePropagateInterestingSymbols(BugReport &R, 01270 InterestingExprs &IE, 01271 const ProgramState *State, 01272 const LocationContext *CalleeCtx, 01273 const LocationContext *CallerCtx) 01274 { 01275 // FIXME: Handle non-CallExpr-based CallEvents. 01276 const StackFrameContext *Callee = CalleeCtx->getCurrentStackFrame(); 01277 const Stmt *CallSite = Callee->getCallSite(); 01278 if (const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite)) { 01279 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CalleeCtx->getDecl())) { 01280 FunctionDecl::param_const_iterator PI = FD->param_begin(), 01281 PE = FD->param_end(); 01282 CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end(); 01283 for (; AI != AE && PI != PE; ++AI, ++PI) { 01284 if (const Expr *ArgE = *AI) { 01285 if (const ParmVarDecl *PD = *PI) { 01286 Loc LV = State->getLValue(PD, CalleeCtx); 01287 if (R.isInteresting(LV) || R.isInteresting(State->getRawSVal(LV))) 01288 IE.insert(ArgE); 01289 } 01290 } 01291 } 01292 } 01293 } 01294 } 01295 01296 //===----------------------------------------------------------------------===// 01297 // Functions for determining if a loop was executed 0 times. 01298 //===----------------------------------------------------------------------===// 01299 01300 static bool isLoop(const Stmt *Term) { 01301 switch (Term->getStmtClass()) { 01302 case Stmt::ForStmtClass: 01303 case Stmt::WhileStmtClass: 01304 case Stmt::ObjCForCollectionStmtClass: 01305 case Stmt::CXXForRangeStmtClass: 01306 return true; 01307 default: 01308 // Note that we intentionally do not include do..while here. 01309 return false; 01310 } 01311 } 01312 01313 static bool isJumpToFalseBranch(const BlockEdge *BE) { 01314 const CFGBlock *Src = BE->getSrc(); 01315 assert(Src->succ_size() == 2); 01316 return (*(Src->succ_begin()+1) == BE->getDst()); 01317 } 01318 01319 /// Return true if the terminator is a loop and the destination is the 01320 /// false branch. 01321 static bool isLoopJumpPastBody(const Stmt *Term, const BlockEdge *BE) { 01322 if (!isLoop(Term)) 01323 return false; 01324 01325 // Did we take the false branch? 01326 return isJumpToFalseBranch(BE); 01327 } 01328 01329 static bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS) { 01330 while (SubS) { 01331 if (SubS == S) 01332 return true; 01333 SubS = PM.getParent(SubS); 01334 } 01335 return false; 01336 } 01337 01338 static const Stmt *getStmtBeforeCond(ParentMap &PM, const Stmt *Term, 01339 const ExplodedNode *N) { 01340 while (N) { 01341 Optional<StmtPoint> SP = N->getLocation().getAs<StmtPoint>(); 01342 if (SP) { 01343 const Stmt *S = SP->getStmt(); 01344 if (!isContainedByStmt(PM, Term, S)) 01345 return S; 01346 } 01347 N = N->getFirstPred(); 01348 } 01349 return nullptr; 01350 } 01351 01352 static bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term) { 01353 const Stmt *LoopBody = nullptr; 01354 switch (Term->getStmtClass()) { 01355 case Stmt::CXXForRangeStmtClass: { 01356 const CXXForRangeStmt *FR = cast<CXXForRangeStmt>(Term); 01357 if (isContainedByStmt(PM, FR->getInc(), S)) 01358 return true; 01359 if (isContainedByStmt(PM, FR->getLoopVarStmt(), S)) 01360 return true; 01361 LoopBody = FR->getBody(); 01362 break; 01363 } 01364 case Stmt::ForStmtClass: { 01365 const ForStmt *FS = cast<ForStmt>(Term); 01366 if (isContainedByStmt(PM, FS->getInc(), S)) 01367 return true; 01368 LoopBody = FS->getBody(); 01369 break; 01370 } 01371 case Stmt::ObjCForCollectionStmtClass: { 01372 const ObjCForCollectionStmt *FC = cast<ObjCForCollectionStmt>(Term); 01373 LoopBody = FC->getBody(); 01374 break; 01375 } 01376 case Stmt::WhileStmtClass: 01377 LoopBody = cast<WhileStmt>(Term)->getBody(); 01378 break; 01379 default: 01380 return false; 01381 } 01382 return isContainedByStmt(PM, LoopBody, S); 01383 } 01384 01385 //===----------------------------------------------------------------------===// 01386 // Top-level logic for generating extensive path diagnostics. 01387 //===----------------------------------------------------------------------===// 01388 01389 static bool GenerateExtensivePathDiagnostic( 01390 PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, 01391 LocationContextMap &LCM, 01392 ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors) { 01393 EdgeBuilder EB(PD, PDB); 01394 const SourceManager& SM = PDB.getSourceManager(); 01395 StackDiagVector CallStack; 01396 InterestingExprs IE; 01397 01398 const ExplodedNode *NextNode = N->pred_empty() ? nullptr : *(N->pred_begin()); 01399 while (NextNode) { 01400 N = NextNode; 01401 NextNode = N->getFirstPred(); 01402 ProgramPoint P = N->getLocation(); 01403 01404 do { 01405 if (Optional<PostStmt> PS = P.getAs<PostStmt>()) { 01406 if (const Expr *Ex = PS->getStmtAs<Expr>()) 01407 reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 01408 N->getState().get(), Ex, 01409 N->getLocationContext()); 01410 } 01411 01412 if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) { 01413 const Stmt *S = CE->getCalleeContext()->getCallSite(); 01414 if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) { 01415 reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 01416 N->getState().get(), Ex, 01417 N->getLocationContext()); 01418 } 01419 01420 PathDiagnosticCallPiece *C = 01421 PathDiagnosticCallPiece::construct(N, *CE, SM); 01422 LCM[&C->path] = CE->getCalleeContext(); 01423 01424 EB.addEdge(C->callReturn, /*AlwaysAdd=*/true, /*IsPostJump=*/true); 01425 EB.flushLocations(); 01426 01427 PD.getActivePath().push_front(C); 01428 PD.pushActivePath(&C->path); 01429 CallStack.push_back(StackDiagPair(C, N)); 01430 break; 01431 } 01432 01433 // Pop the call hierarchy if we are done walking the contents 01434 // of a function call. 01435 if (Optional<CallEnter> CE = P.getAs<CallEnter>()) { 01436 // Add an edge to the start of the function. 01437 const Decl *D = CE->getCalleeContext()->getDecl(); 01438 PathDiagnosticLocation pos = 01439 PathDiagnosticLocation::createBegin(D, SM); 01440 EB.addEdge(pos); 01441 01442 // Flush all locations, and pop the active path. 01443 bool VisitedEntireCall = PD.isWithinCall(); 01444 EB.flushLocations(); 01445 PD.popActivePath(); 01446 PDB.LC = N->getLocationContext(); 01447 01448 // Either we just added a bunch of stuff to the top-level path, or 01449 // we have a previous CallExitEnd. If the former, it means that the 01450 // path terminated within a function call. We must then take the 01451 // current contents of the active path and place it within 01452 // a new PathDiagnosticCallPiece. 01453 PathDiagnosticCallPiece *C; 01454 if (VisitedEntireCall) { 01455 C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); 01456 } else { 01457 const Decl *Caller = CE->getLocationContext()->getDecl(); 01458 C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 01459 LCM[&C->path] = CE->getCalleeContext(); 01460 } 01461 01462 C->setCallee(*CE, SM); 01463 EB.addContext(C->getLocation()); 01464 01465 if (!CallStack.empty()) { 01466 assert(CallStack.back().first == C); 01467 CallStack.pop_back(); 01468 } 01469 break; 01470 } 01471 01472 // Note that is important that we update the LocationContext 01473 // after looking at CallExits. CallExit basically adds an 01474 // edge in the *caller*, so we don't want to update the LocationContext 01475 // too soon. 01476 PDB.LC = N->getLocationContext(); 01477 01478 // Block edges. 01479 if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) { 01480 // Does this represent entering a call? If so, look at propagating 01481 // interesting symbols across call boundaries. 01482 if (NextNode) { 01483 const LocationContext *CallerCtx = NextNode->getLocationContext(); 01484 const LocationContext *CalleeCtx = PDB.LC; 01485 if (CallerCtx != CalleeCtx) { 01486 reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, 01487 N->getState().get(), 01488 CalleeCtx, CallerCtx); 01489 } 01490 } 01491 01492 // Are we jumping to the head of a loop? Add a special diagnostic. 01493 if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { 01494 PathDiagnosticLocation L(Loop, SM, PDB.LC); 01495 const CompoundStmt *CS = nullptr; 01496 01497 if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) 01498 CS = dyn_cast<CompoundStmt>(FS->getBody()); 01499 else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) 01500 CS = dyn_cast<CompoundStmt>(WS->getBody()); 01501 01502 PathDiagnosticEventPiece *p = 01503 new PathDiagnosticEventPiece(L, 01504 "Looping back to the head of the loop"); 01505 p->setPrunable(true); 01506 01507 EB.addEdge(p->getLocation(), true); 01508 PD.getActivePath().push_front(p); 01509 01510 if (CS) { 01511 PathDiagnosticLocation BL = 01512 PathDiagnosticLocation::createEndBrace(CS, SM); 01513 EB.addEdge(BL); 01514 } 01515 } 01516 01517 const CFGBlock *BSrc = BE->getSrc(); 01518 ParentMap &PM = PDB.getParentMap(); 01519 01520 if (const Stmt *Term = BSrc->getTerminator()) { 01521 // Are we jumping past the loop body without ever executing the 01522 // loop (because the condition was false)? 01523 if (isLoopJumpPastBody(Term, &*BE) && 01524 !isInLoopBody(PM, 01525 getStmtBeforeCond(PM, 01526 BSrc->getTerminatorCondition(), 01527 N), 01528 Term)) { 01529 PathDiagnosticLocation L(Term, SM, PDB.LC); 01530 PathDiagnosticEventPiece *PE = 01531 new PathDiagnosticEventPiece(L, "Loop body executed 0 times"); 01532 PE->setPrunable(true); 01533 01534 EB.addEdge(PE->getLocation(), true); 01535 PD.getActivePath().push_front(PE); 01536 } 01537 01538 // In any case, add the terminator as the current statement 01539 // context for control edges. 01540 EB.addContext(Term); 01541 } 01542 01543 break; 01544 } 01545 01546 if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) { 01547 Optional<CFGElement> First = BE->getFirstElement(); 01548 if (Optional<CFGStmt> S = First ? First->getAs<CFGStmt>() : None) { 01549 const Stmt *stmt = S->getStmt(); 01550 if (IsControlFlowExpr(stmt)) { 01551 // Add the proper context for '&&', '||', and '?'. 01552 EB.addContext(stmt); 01553 } 01554 else 01555 EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt()); 01556 } 01557 01558 break; 01559 } 01560 01561 01562 } while (0); 01563 01564 if (!NextNode) 01565 continue; 01566 01567 // Add pieces from custom visitors. 01568 BugReport *R = PDB.getBugReport(); 01569 for (auto &V : visitors) { 01570 if (PathDiagnosticPiece *p = V->VisitNode(N, NextNode, PDB, *R)) { 01571 const PathDiagnosticLocation &Loc = p->getLocation(); 01572 EB.addEdge(Loc, true); 01573 PD.getActivePath().push_front(p); 01574 updateStackPiecesWithMessage(p, CallStack); 01575 01576 if (const Stmt *S = Loc.asStmt()) 01577 EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); 01578 } 01579 } 01580 } 01581 01582 return PDB.getBugReport()->isValid(); 01583 } 01584 01585 /// \brief Adds a sanitized control-flow diagnostic edge to a path. 01586 static void addEdgeToPath(PathPieces &path, 01587 PathDiagnosticLocation &PrevLoc, 01588 PathDiagnosticLocation NewLoc, 01589 const LocationContext *LC) { 01590 if (!NewLoc.isValid()) 01591 return; 01592 01593 SourceLocation NewLocL = NewLoc.asLocation(); 01594 if (NewLocL.isInvalid()) 01595 return; 01596 01597 if (!PrevLoc.isValid() || !PrevLoc.asLocation().isValid()) { 01598 PrevLoc = NewLoc; 01599 return; 01600 } 01601 01602 // Ignore self-edges, which occur when there are multiple nodes at the same 01603 // statement. 01604 if (NewLoc.asStmt() && NewLoc.asStmt() == PrevLoc.asStmt()) 01605 return; 01606 01607 path.push_front(new PathDiagnosticControlFlowPiece(NewLoc, 01608 PrevLoc)); 01609 PrevLoc = NewLoc; 01610 } 01611 01612 /// A customized wrapper for CFGBlock::getTerminatorCondition() 01613 /// which returns the element for ObjCForCollectionStmts. 01614 static const Stmt *getTerminatorCondition(const CFGBlock *B) { 01615 const Stmt *S = B->getTerminatorCondition(); 01616 if (const ObjCForCollectionStmt *FS = 01617 dyn_cast_or_null<ObjCForCollectionStmt>(S)) 01618 return FS->getElement(); 01619 return S; 01620 } 01621 01622 static const char StrEnteringLoop[] = "Entering loop body"; 01623 static const char StrLoopBodyZero[] = "Loop body executed 0 times"; 01624 static const char StrLoopRangeEmpty[] = 01625 "Loop body skipped when range is empty"; 01626 static const char StrLoopCollectionEmpty[] = 01627 "Loop body skipped when collection is empty"; 01628 01629 static bool GenerateAlternateExtensivePathDiagnostic( 01630 PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, 01631 LocationContextMap &LCM, 01632 ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors) { 01633 01634 BugReport *report = PDB.getBugReport(); 01635 const SourceManager& SM = PDB.getSourceManager(); 01636 StackDiagVector CallStack; 01637 InterestingExprs IE; 01638 01639 PathDiagnosticLocation PrevLoc = PD.getLocation(); 01640 01641 const ExplodedNode *NextNode = N->getFirstPred(); 01642 while (NextNode) { 01643 N = NextNode; 01644 NextNode = N->getFirstPred(); 01645 ProgramPoint P = N->getLocation(); 01646 01647 do { 01648 // Have we encountered an entrance to a call? It may be 01649 // the case that we have not encountered a matching 01650 // call exit before this point. This means that the path 01651 // terminated within the call itself. 01652 if (Optional<CallEnter> CE = P.getAs<CallEnter>()) { 01653 // Add an edge to the start of the function. 01654 const StackFrameContext *CalleeLC = CE->getCalleeContext(); 01655 const Decl *D = CalleeLC->getDecl(); 01656 addEdgeToPath(PD.getActivePath(), PrevLoc, 01657 PathDiagnosticLocation::createBegin(D, SM), 01658 CalleeLC); 01659 01660 // Did we visit an entire call? 01661 bool VisitedEntireCall = PD.isWithinCall(); 01662 PD.popActivePath(); 01663 01664 PathDiagnosticCallPiece *C; 01665 if (VisitedEntireCall) { 01666 PathDiagnosticPiece *P = PD.getActivePath().front().get(); 01667 C = cast<PathDiagnosticCallPiece>(P); 01668 } else { 01669 const Decl *Caller = CE->getLocationContext()->getDecl(); 01670 C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); 01671 01672 // Since we just transferred the path over to the call piece, 01673 // reset the mapping from active to location context. 01674 assert(PD.getActivePath().size() == 1 && 01675 PD.getActivePath().front() == C); 01676 LCM[&PD.getActivePath()] = nullptr; 01677 01678 // Record the location context mapping for the path within 01679 // the call. 01680 assert(LCM[&C->path] == nullptr || 01681 LCM[&C->path] == CE->getCalleeContext()); 01682 LCM[&C->path] = CE->getCalleeContext(); 01683 01684 // If this is the first item in the active path, record 01685 // the new mapping from active path to location context. 01686 const LocationContext *&NewLC = LCM[&PD.getActivePath()]; 01687 if (!NewLC) 01688 NewLC = N->getLocationContext(); 01689 01690 PDB.LC = NewLC; 01691 } 01692 C->setCallee(*CE, SM); 01693 01694 // Update the previous location in the active path. 01695 PrevLoc = C->getLocation(); 01696 01697 if (!CallStack.empty()) { 01698 assert(CallStack.back().first == C); 01699 CallStack.pop_back(); 01700 } 01701 break; 01702 } 01703 01704 // Query the location context here and the previous location 01705 // as processing CallEnter may change the active path. 01706 PDB.LC = N->getLocationContext(); 01707 01708 // Record the mapping from the active path to the location 01709 // context. 01710 assert(!LCM[&PD.getActivePath()] || 01711 LCM[&PD.getActivePath()] == PDB.LC); 01712 LCM[&PD.getActivePath()] = PDB.LC; 01713 01714 // Have we encountered an exit from a function call? 01715 if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) { 01716 const Stmt *S = CE->getCalleeContext()->getCallSite(); 01717 // Propagate the interesting symbols accordingly. 01718 if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) { 01719 reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 01720 N->getState().get(), Ex, 01721 N->getLocationContext()); 01722 } 01723 01724 // We are descending into a call (backwards). Construct 01725 // a new call piece to contain the path pieces for that call. 01726 PathDiagnosticCallPiece *C = 01727 PathDiagnosticCallPiece::construct(N, *CE, SM); 01728 01729 // Record the location context for this call piece. 01730 LCM[&C->path] = CE->getCalleeContext(); 01731 01732 // Add the edge to the return site. 01733 addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, PDB.LC); 01734 PD.getActivePath().push_front(C); 01735 PrevLoc.invalidate(); 01736 01737 // Make the contents of the call the active path for now. 01738 PD.pushActivePath(&C->path); 01739 CallStack.push_back(StackDiagPair(C, N)); 01740 break; 01741 } 01742 01743 if (Optional<PostStmt> PS = P.getAs<PostStmt>()) { 01744 // For expressions, make sure we propagate the 01745 // interesting symbols correctly. 01746 if (const Expr *Ex = PS->getStmtAs<Expr>()) 01747 reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, 01748 N->getState().get(), Ex, 01749 N->getLocationContext()); 01750 01751 // Add an edge. If this is an ObjCForCollectionStmt do 01752 // not add an edge here as it appears in the CFG both 01753 // as a terminator and as a terminator condition. 01754 if (!isa<ObjCForCollectionStmt>(PS->getStmt())) { 01755 PathDiagnosticLocation L = 01756 PathDiagnosticLocation(PS->getStmt(), SM, PDB.LC); 01757 addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); 01758 } 01759 break; 01760 } 01761 01762 // Block edges. 01763 if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) { 01764 // Does this represent entering a call? If so, look at propagating 01765 // interesting symbols across call boundaries. 01766 if (NextNode) { 01767 const LocationContext *CallerCtx = NextNode->getLocationContext(); 01768 const LocationContext *CalleeCtx = PDB.LC; 01769 if (CallerCtx != CalleeCtx) { 01770 reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, 01771 N->getState().get(), 01772 CalleeCtx, CallerCtx); 01773 } 01774 } 01775 01776 // Are we jumping to the head of a loop? Add a special diagnostic. 01777 if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { 01778 PathDiagnosticLocation L(Loop, SM, PDB.LC); 01779 const Stmt *Body = nullptr; 01780 01781 if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) 01782 Body = FS->getBody(); 01783 else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) 01784 Body = WS->getBody(); 01785 else if (const ObjCForCollectionStmt *OFS = 01786 dyn_cast<ObjCForCollectionStmt>(Loop)) { 01787 Body = OFS->getBody(); 01788 } else if (const CXXForRangeStmt *FRS = 01789 dyn_cast<CXXForRangeStmt>(Loop)) { 01790 Body = FRS->getBody(); 01791 } 01792 // do-while statements are explicitly excluded here 01793 01794 PathDiagnosticEventPiece *p = 01795 new PathDiagnosticEventPiece(L, "Looping back to the head " 01796 "of the loop"); 01797 p->setPrunable(true); 01798 01799 addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC); 01800 PD.getActivePath().push_front(p); 01801 01802 if (const CompoundStmt *CS = dyn_cast_or_null<CompoundStmt>(Body)) { 01803 addEdgeToPath(PD.getActivePath(), PrevLoc, 01804 PathDiagnosticLocation::createEndBrace(CS, SM), 01805 PDB.LC); 01806 } 01807 } 01808 01809 const CFGBlock *BSrc = BE->getSrc(); 01810 ParentMap &PM = PDB.getParentMap(); 01811 01812 if (const Stmt *Term = BSrc->getTerminator()) { 01813 // Are we jumping past the loop body without ever executing the 01814 // loop (because the condition was false)? 01815 if (isLoop(Term)) { 01816 const Stmt *TermCond = getTerminatorCondition(BSrc); 01817 bool IsInLoopBody = 01818 isInLoopBody(PM, getStmtBeforeCond(PM, TermCond, N), Term); 01819 01820 const char *str = nullptr; 01821 01822 if (isJumpToFalseBranch(&*BE)) { 01823 if (!IsInLoopBody) { 01824 if (isa<ObjCForCollectionStmt>(Term)) { 01825 str = StrLoopCollectionEmpty; 01826 } else if (isa<CXXForRangeStmt>(Term)) { 01827 str = StrLoopRangeEmpty; 01828 } else { 01829 str = StrLoopBodyZero; 01830 } 01831 } 01832 } else { 01833 str = StrEnteringLoop; 01834 } 01835 01836 if (str) { 01837 PathDiagnosticLocation L(TermCond ? TermCond : Term, SM, PDB.LC); 01838 PathDiagnosticEventPiece *PE = 01839 new PathDiagnosticEventPiece(L, str); 01840 PE->setPrunable(true); 01841 addEdgeToPath(PD.getActivePath(), PrevLoc, 01842 PE->getLocation(), PDB.LC); 01843 PD.getActivePath().push_front(PE); 01844 } 01845 } else if (isa<BreakStmt>(Term) || isa<ContinueStmt>(Term) || 01846 isa<GotoStmt>(Term)) { 01847 PathDiagnosticLocation L(Term, SM, PDB.LC); 01848 addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); 01849 } 01850 } 01851 break; 01852 } 01853 } while (0); 01854 01855 if (!NextNode) 01856 continue; 01857 01858 // Add pieces from custom visitors. 01859 for (auto &V : visitors) { 01860 if (PathDiagnosticPiece *p = V->VisitNode(N, NextNode, PDB, *report)) { 01861 addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC); 01862 PD.getActivePath().push_front(p); 01863 updateStackPiecesWithMessage(p, CallStack); 01864 } 01865 } 01866 } 01867 01868 // Add an edge to the start of the function. 01869 // We'll prune it out later, but it helps make diagnostics more uniform. 01870 const StackFrameContext *CalleeLC = PDB.LC->getCurrentStackFrame(); 01871 const Decl *D = CalleeLC->getDecl(); 01872 addEdgeToPath(PD.getActivePath(), PrevLoc, 01873 PathDiagnosticLocation::createBegin(D, SM), 01874 CalleeLC); 01875 01876 return report->isValid(); 01877 } 01878 01879 static const Stmt *getLocStmt(PathDiagnosticLocation L) { 01880 if (!L.isValid()) 01881 return nullptr; 01882 return L.asStmt(); 01883 } 01884 01885 static const Stmt *getStmtParent(const Stmt *S, const ParentMap &PM) { 01886 if (!S) 01887 return nullptr; 01888 01889 while (true) { 01890 S = PM.getParentIgnoreParens(S); 01891 01892 if (!S) 01893 break; 01894 01895 if (isa<ExprWithCleanups>(S) || 01896 isa<CXXBindTemporaryExpr>(S) || 01897 isa<SubstNonTypeTemplateParmExpr>(S)) 01898 continue; 01899 01900 break; 01901 } 01902 01903 return S; 01904 } 01905 01906 static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) { 01907 switch (S->getStmtClass()) { 01908 case Stmt::BinaryOperatorClass: { 01909 const BinaryOperator *BO = cast<BinaryOperator>(S); 01910 if (!BO->isLogicalOp()) 01911 return false; 01912 return BO->getLHS() == Cond || BO->getRHS() == Cond; 01913 } 01914 case Stmt::IfStmtClass: 01915 return cast<IfStmt>(S)->getCond() == Cond; 01916 case Stmt::ForStmtClass: 01917 return cast<ForStmt>(S)->getCond() == Cond; 01918 case Stmt::WhileStmtClass: 01919 return cast<WhileStmt>(S)->getCond() == Cond; 01920 case Stmt::DoStmtClass: 01921 return cast<DoStmt>(S)->getCond() == Cond; 01922 case Stmt::ChooseExprClass: 01923 return cast<ChooseExpr>(S)->getCond() == Cond; 01924 case Stmt::IndirectGotoStmtClass: 01925 return cast<IndirectGotoStmt>(S)->getTarget() == Cond; 01926 case Stmt::SwitchStmtClass: 01927 return cast<SwitchStmt>(S)->getCond() == Cond; 01928 case Stmt::BinaryConditionalOperatorClass: 01929 return cast<BinaryConditionalOperator>(S)->getCond() == Cond; 01930 case Stmt::ConditionalOperatorClass: { 01931 const ConditionalOperator *CO = cast<ConditionalOperator>(S); 01932 return CO->getCond() == Cond || 01933 CO->getLHS() == Cond || 01934 CO->getRHS() == Cond; 01935 } 01936 case Stmt::ObjCForCollectionStmtClass: 01937 return cast<ObjCForCollectionStmt>(S)->getElement() == Cond; 01938 case Stmt::CXXForRangeStmtClass: { 01939 const CXXForRangeStmt *FRS = cast<CXXForRangeStmt>(S); 01940 return FRS->getCond() == Cond || FRS->getRangeInit() == Cond; 01941 } 01942 default: 01943 return false; 01944 } 01945 } 01946 01947 static bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL) { 01948 if (const ForStmt *FS = dyn_cast<ForStmt>(FL)) 01949 return FS->getInc() == S || FS->getInit() == S; 01950 if (const CXXForRangeStmt *FRS = dyn_cast<CXXForRangeStmt>(FL)) 01951 return FRS->getInc() == S || FRS->getRangeStmt() == S || 01952 FRS->getLoopVarStmt() || FRS->getRangeInit() == S; 01953 return false; 01954 } 01955 01956 typedef llvm::DenseSet<const PathDiagnosticCallPiece *> 01957 OptimizedCallsSet; 01958 01959 /// Adds synthetic edges from top-level statements to their subexpressions. 01960 /// 01961 /// This avoids a "swoosh" effect, where an edge from a top-level statement A 01962 /// points to a sub-expression B.1 that's not at the start of B. In these cases, 01963 /// we'd like to see an edge from A to B, then another one from B to B.1. 01964 static void addContextEdges(PathPieces &pieces, SourceManager &SM, 01965 const ParentMap &PM, const LocationContext *LCtx) { 01966 PathPieces::iterator Prev = pieces.end(); 01967 for (PathPieces::iterator I = pieces.begin(), E = Prev; I != E; 01968 Prev = I, ++I) { 01969 PathDiagnosticControlFlowPiece *Piece = 01970 dyn_cast<PathDiagnosticControlFlowPiece>(*I); 01971 01972 if (!Piece) 01973 continue; 01974 01975 PathDiagnosticLocation SrcLoc = Piece->getStartLocation(); 01976 SmallVector<PathDiagnosticLocation, 4> SrcContexts; 01977 01978 PathDiagnosticLocation NextSrcContext = SrcLoc; 01979 const Stmt *InnerStmt = nullptr; 01980 while (NextSrcContext.isValid() && NextSrcContext.asStmt() != InnerStmt) { 01981 SrcContexts.push_back(NextSrcContext); 01982 InnerStmt = NextSrcContext.asStmt(); 01983 NextSrcContext = getEnclosingStmtLocation(InnerStmt, SM, PM, LCtx, 01984 /*allowNested=*/true); 01985 } 01986 01987 // Repeatedly split the edge as necessary. 01988 // This is important for nested logical expressions (||, &&, ?:) where we 01989 // want to show all the levels of context. 01990 while (true) { 01991 const Stmt *Dst = getLocStmt(Piece->getEndLocation()); 01992 01993 // We are looking at an edge. Is the destination within a larger 01994 // expression? 01995 PathDiagnosticLocation DstContext = 01996 getEnclosingStmtLocation(Dst, SM, PM, LCtx, /*allowNested=*/true); 01997 if (!DstContext.isValid() || DstContext.asStmt() == Dst) 01998 break; 01999 02000 // If the source is in the same context, we're already good. 02001 if (std::find(SrcContexts.begin(), SrcContexts.end(), DstContext) != 02002 SrcContexts.end()) 02003 break; 02004 02005 // Update the subexpression node to point to the context edge. 02006 Piece->setStartLocation(DstContext); 02007 02008 // Try to extend the previous edge if it's at the same level as the source 02009 // context. 02010 if (Prev != E) { 02011 PathDiagnosticControlFlowPiece *PrevPiece = 02012 dyn_cast<PathDiagnosticControlFlowPiece>(*Prev); 02013 02014 if (PrevPiece) { 02015 if (const Stmt *PrevSrc = getLocStmt(PrevPiece->getStartLocation())) { 02016 const Stmt *PrevSrcParent = getStmtParent(PrevSrc, PM); 02017 if (PrevSrcParent == getStmtParent(getLocStmt(DstContext), PM)) { 02018 PrevPiece->setEndLocation(DstContext); 02019 break; 02020 } 02021 } 02022 } 02023 } 02024 02025 // Otherwise, split the current edge into a context edge and a 02026 // subexpression edge. Note that the context statement may itself have 02027 // context. 02028 Piece = new PathDiagnosticControlFlowPiece(SrcLoc, DstContext); 02029 I = pieces.insert(I, Piece); 02030 } 02031 } 02032 } 02033 02034 /// \brief Move edges from a branch condition to a branch target 02035 /// when the condition is simple. 02036 /// 02037 /// This restructures some of the work of addContextEdges. That function 02038 /// creates edges this may destroy, but they work together to create a more 02039 /// aesthetically set of edges around branches. After the call to 02040 /// addContextEdges, we may have (1) an edge to the branch, (2) an edge from 02041 /// the branch to the branch condition, and (3) an edge from the branch 02042 /// condition to the branch target. We keep (1), but may wish to remove (2) 02043 /// and move the source of (3) to the branch if the branch condition is simple. 02044 /// 02045 static void simplifySimpleBranches(PathPieces &pieces) { 02046 for (PathPieces::iterator I = pieces.begin(), E = pieces.end(); I != E; ++I) { 02047 02048 PathDiagnosticControlFlowPiece *PieceI = 02049 dyn_cast<PathDiagnosticControlFlowPiece>(*I); 02050 02051 if (!PieceI) 02052 continue; 02053 02054 const Stmt *s1Start = getLocStmt(PieceI->getStartLocation()); 02055 const Stmt *s1End = getLocStmt(PieceI->getEndLocation()); 02056 02057 if (!s1Start || !s1End) 02058 continue; 02059 02060 PathPieces::iterator NextI = I; ++NextI; 02061 if (NextI == E) 02062 break; 02063 02064 PathDiagnosticControlFlowPiece *PieceNextI = nullptr; 02065 02066 while (true) { 02067 if (NextI == E) 02068 break; 02069 02070 PathDiagnosticEventPiece *EV = dyn_cast<PathDiagnosticEventPiece>(*NextI); 02071 if (EV) { 02072 StringRef S = EV->getString(); 02073 if (S == StrEnteringLoop || S == StrLoopBodyZero || 02074 S == StrLoopCollectionEmpty || S == StrLoopRangeEmpty) { 02075 ++NextI; 02076 continue; 02077 } 02078 break; 02079 } 02080 02081 PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); 02082 break; 02083 } 02084 02085 if (!PieceNextI) 02086 continue; 02087 02088 const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation()); 02089 const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation()); 02090 02091 if (!s2Start || !s2End || s1End != s2Start) 02092 continue; 02093 02094 // We only perform this transformation for specific branch kinds. 02095 // We don't want to do this for do..while, for example. 02096 if (!(isa<ForStmt>(s1Start) || isa<WhileStmt>(s1Start) || 02097 isa<IfStmt>(s1Start) || isa<ObjCForCollectionStmt>(s1Start) || 02098 isa<CXXForRangeStmt>(s1Start))) 02099 continue; 02100 02101 // Is s1End the branch condition? 02102 if (!isConditionForTerminator(s1Start, s1End)) 02103 continue; 02104 02105 // Perform the hoisting by eliminating (2) and changing the start 02106 // location of (3). 02107 PieceNextI->setStartLocation(PieceI->getStartLocation()); 02108 I = pieces.erase(I); 02109 } 02110 } 02111 02112 /// Returns the number of bytes in the given (character-based) SourceRange. 02113 /// 02114 /// If the locations in the range are not on the same line, returns None. 02115 /// 02116 /// Note that this does not do a precise user-visible character or column count. 02117 static Optional<size_t> getLengthOnSingleLine(SourceManager &SM, 02118 SourceRange Range) { 02119 SourceRange ExpansionRange(SM.getExpansionLoc(Range.getBegin()), 02120 SM.getExpansionRange(Range.getEnd()).second); 02121 02122 FileID FID = SM.getFileID(ExpansionRange.getBegin()); 02123 if (FID != SM.getFileID(ExpansionRange.getEnd())) 02124 return None; 02125 02126 bool Invalid; 02127 const llvm::MemoryBuffer *Buffer = SM.getBuffer(FID, &Invalid); 02128 if (Invalid) 02129 return None; 02130 02131 unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin()); 02132 unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd()); 02133 StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset); 02134 02135 // We're searching the raw bytes of the buffer here, which might include 02136 // escaped newlines and such. That's okay; we're trying to decide whether the 02137 // SourceRange is covering a large or small amount of space in the user's 02138 // editor. 02139 if (Snippet.find_first_of("\r\n") != StringRef::npos) 02140 return None; 02141 02142 // This isn't Unicode-aware, but it doesn't need to be. 02143 return Snippet.size(); 02144 } 02145 02146 /// \sa getLengthOnSingleLine(SourceManager, SourceRange) 02147 static Optional<size_t> getLengthOnSingleLine(SourceManager &SM, 02148 const Stmt *S) { 02149 return getLengthOnSingleLine(SM, S->getSourceRange()); 02150 } 02151 02152 /// Eliminate two-edge cycles created by addContextEdges(). 02153 /// 02154 /// Once all the context edges are in place, there are plenty of cases where 02155 /// there's a single edge from a top-level statement to a subexpression, 02156 /// followed by a single path note, and then a reverse edge to get back out to 02157 /// the top level. If the statement is simple enough, the subexpression edges 02158 /// just add noise and make it harder to understand what's going on. 02159 /// 02160 /// This function only removes edges in pairs, because removing only one edge 02161 /// might leave other edges dangling. 02162 /// 02163 /// This will not remove edges in more complicated situations: 02164 /// - if there is more than one "hop" leading to or from a subexpression. 02165 /// - if there is an inlined call between the edges instead of a single event. 02166 /// - if the whole statement is large enough that having subexpression arrows 02167 /// might be helpful. 02168 static void removeContextCycles(PathPieces &Path, SourceManager &SM, 02169 ParentMap &PM) { 02170 for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) { 02171 // Pattern match the current piece and its successor. 02172 PathDiagnosticControlFlowPiece *PieceI = 02173 dyn_cast<PathDiagnosticControlFlowPiece>(*I); 02174 02175 if (!PieceI) { 02176 ++I; 02177 continue; 02178 } 02179 02180 const Stmt *s1Start = getLocStmt(PieceI->getStartLocation()); 02181 const Stmt *s1End = getLocStmt(PieceI->getEndLocation()); 02182 02183 PathPieces::iterator NextI = I; ++NextI; 02184 if (NextI == E) 02185 break; 02186 02187 PathDiagnosticControlFlowPiece *PieceNextI = 02188 dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); 02189 02190 if (!PieceNextI) { 02191 if (isa<PathDiagnosticEventPiece>(*NextI)) { 02192 ++NextI; 02193 if (NextI == E) 02194 break; 02195 PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); 02196 } 02197 02198 if (!PieceNextI) { 02199 ++I; 02200 continue; 02201 } 02202 } 02203 02204 const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation()); 02205 const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation()); 02206 02207 if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) { 02208 const size_t MAX_SHORT_LINE_LENGTH = 80; 02209 Optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start); 02210 if (s1Length && *s1Length <= MAX_SHORT_LINE_LENGTH) { 02211 Optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start); 02212 if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) { 02213 Path.erase(I); 02214 I = Path.erase(NextI); 02215 continue; 02216 } 02217 } 02218 } 02219 02220 ++I; 02221 } 02222 } 02223 02224 /// \brief Return true if X is contained by Y. 02225 static bool lexicalContains(ParentMap &PM, 02226 const Stmt *X, 02227 const Stmt *Y) { 02228 while (X) { 02229 if (X == Y) 02230 return true; 02231 X = PM.getParent(X); 02232 } 02233 return false; 02234 } 02235 02236 // Remove short edges on the same line less than 3 columns in difference. 02237 static void removePunyEdges(PathPieces &path, 02238 SourceManager &SM, 02239 ParentMap &PM) { 02240 02241 bool erased = false; 02242 02243 for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; 02244 erased ? I : ++I) { 02245 02246 erased = false; 02247 02248 PathDiagnosticControlFlowPiece *PieceI = 02249 dyn_cast<PathDiagnosticControlFlowPiece>(*I); 02250 02251 if (!PieceI) 02252 continue; 02253 02254 const Stmt *start = getLocStmt(PieceI->getStartLocation()); 02255 const Stmt *end = getLocStmt(PieceI->getEndLocation()); 02256 02257 if (!start || !end) 02258 continue; 02259 02260 const Stmt *endParent = PM.getParent(end); 02261 if (!endParent) 02262 continue; 02263 02264 if (isConditionForTerminator(end, endParent)) 02265 continue; 02266 02267 SourceLocation FirstLoc = start->getLocStart(); 02268 SourceLocation SecondLoc = end->getLocStart(); 02269 02270 if (!SM.isWrittenInSameFile(FirstLoc, SecondLoc)) 02271 continue; 02272 if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc)) 02273 std::swap(SecondLoc, FirstLoc); 02274 02275 SourceRange EdgeRange(FirstLoc, SecondLoc); 02276 Optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange); 02277 02278 // If the statements are on different lines, continue. 02279 if (!ByteWidth) 02280 continue; 02281 02282 const size_t MAX_PUNY_EDGE_LENGTH = 2; 02283 if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) { 02284 // FIXME: There are enough /bytes/ between the endpoints of the edge, but 02285 // there might not be enough /columns/. A proper user-visible column count 02286 // is probably too expensive, though. 02287 I = path.erase(I); 02288 erased = true; 02289 continue; 02290 } 02291 } 02292 } 02293 02294 static void removeIdenticalEvents(PathPieces &path) { 02295 for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) { 02296 PathDiagnosticEventPiece *PieceI = 02297 dyn_cast<PathDiagnosticEventPiece>(*I); 02298 02299 if (!PieceI) 02300 continue; 02301 02302 PathPieces::iterator NextI = I; ++NextI; 02303 if (NextI == E) 02304 return; 02305 02306 PathDiagnosticEventPiece *PieceNextI = 02307 dyn_cast<PathDiagnosticEventPiece>(*NextI); 02308 02309 if (!PieceNextI) 02310 continue; 02311 02312 // Erase the second piece if it has the same exact message text. 02313 if (PieceI->getString() == PieceNextI->getString()) { 02314 path.erase(NextI); 02315 } 02316 } 02317 } 02318 02319 static bool optimizeEdges(PathPieces &path, SourceManager &SM, 02320 OptimizedCallsSet &OCS, 02321 LocationContextMap &LCM) { 02322 bool hasChanges = false; 02323 const LocationContext *LC = LCM[&path]; 02324 assert(LC); 02325 ParentMap &PM = LC->getParentMap(); 02326 02327 for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) { 02328 // Optimize subpaths. 02329 if (PathDiagnosticCallPiece *CallI = dyn_cast<PathDiagnosticCallPiece>(*I)){ 02330 // Record the fact that a call has been optimized so we only do the 02331 // effort once. 02332 if (!OCS.count(CallI)) { 02333 while (optimizeEdges(CallI->path, SM, OCS, LCM)) {} 02334 OCS.insert(CallI); 02335 } 02336 ++I; 02337 continue; 02338 } 02339 02340 // Pattern match the current piece and its successor. 02341 PathDiagnosticControlFlowPiece *PieceI = 02342 dyn_cast<PathDiagnosticControlFlowPiece>(*I); 02343 02344 if (!PieceI) { 02345 ++I; 02346 continue; 02347 } 02348 02349 const Stmt *s1Start = getLocStmt(PieceI->getStartLocation()); 02350 const Stmt *s1End = getLocStmt(PieceI->getEndLocation()); 02351 const Stmt *level1 = getStmtParent(s1Start, PM); 02352 const Stmt *level2 = getStmtParent(s1End, PM); 02353 02354 PathPieces::iterator NextI = I; ++NextI; 02355 if (NextI == E) 02356 break; 02357 02358 PathDiagnosticControlFlowPiece *PieceNextI = 02359 dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); 02360 02361 if (!PieceNextI) { 02362 ++I; 02363 continue; 02364 } 02365 02366 const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation()); 02367 const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation()); 02368 const Stmt *level3 = getStmtParent(s2Start, PM); 02369 const Stmt *level4 = getStmtParent(s2End, PM); 02370 02371 // Rule I. 02372 // 02373 // If we have two consecutive control edges whose end/begin locations 02374 // are at the same level (e.g. statements or top-level expressions within 02375 // a compound statement, or siblings share a single ancestor expression), 02376 // then merge them if they have no interesting intermediate event. 02377 // 02378 // For example: 02379 // 02380 // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common 02381 // parent is '1'. Here 'x.y.z' represents the hierarchy of statements. 02382 // 02383 // NOTE: this will be limited later in cases where we add barriers 02384 // to prevent this optimization. 02385 // 02386 if (level1 && level1 == level2 && level1 == level3 && level1 == level4) { 02387 PieceI->setEndLocation(PieceNextI->getEndLocation()); 02388 path.erase(NextI); 02389 hasChanges = true; 02390 continue; 02391 } 02392 02393 // Rule II. 02394 // 02395 // Eliminate edges between subexpressions and parent expressions 02396 // when the subexpression is consumed. 02397 // 02398 // NOTE: this will be limited later in cases where we add barriers 02399 // to prevent this optimization. 02400 // 02401 if (s1End && s1End == s2Start && level2) { 02402 bool removeEdge = false; 02403 // Remove edges into the increment or initialization of a 02404 // loop that have no interleaving event. This means that 02405 // they aren't interesting. 02406 if (isIncrementOrInitInForLoop(s1End, level2)) 02407 removeEdge = true; 02408 // Next only consider edges that are not anchored on 02409 // the condition of a terminator. This are intermediate edges 02410 // that we might want to trim. 02411 else if (!isConditionForTerminator(level2, s1End)) { 02412 // Trim edges on expressions that are consumed by 02413 // the parent expression. 02414 if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) { 02415 removeEdge = true; 02416 } 02417 // Trim edges where a lexical containment doesn't exist. 02418 // For example: 02419 // 02420 // X -> Y -> Z 02421 // 02422 // If 'Z' lexically contains Y (it is an ancestor) and 02423 // 'X' does not lexically contain Y (it is a descendant OR 02424 // it has no lexical relationship at all) then trim. 02425 // 02426 // This can eliminate edges where we dive into a subexpression 02427 // and then pop back out, etc. 02428 else if (s1Start && s2End && 02429 lexicalContains(PM, s2Start, s2End) && 02430 !lexicalContains(PM, s1End, s1Start)) { 02431 removeEdge = true; 02432 } 02433 // Trim edges from a subexpression back to the top level if the 02434 // subexpression is on a different line. 02435 // 02436 // A.1 -> A -> B 02437 // becomes 02438 // A.1 -> B 02439 // 02440 // These edges just look ugly and don't usually add anything. 02441 else if (s1Start && s2End && 02442 lexicalContains(PM, s1Start, s1End)) { 02443 SourceRange EdgeRange(PieceI->getEndLocation().asLocation(), 02444 PieceI->getStartLocation().asLocation()); 02445 if (!getLengthOnSingleLine(SM, EdgeRange).hasValue()) 02446 removeEdge = true; 02447 } 02448 } 02449 02450 if (removeEdge) { 02451 PieceI->setEndLocation(PieceNextI->getEndLocation()); 02452 path.erase(NextI); 02453 hasChanges = true; 02454 continue; 02455 } 02456 } 02457 02458 // Optimize edges for ObjC fast-enumeration loops. 02459 // 02460 // (X -> collection) -> (collection -> element) 02461 // 02462 // becomes: 02463 // 02464 // (X -> element) 02465 if (s1End == s2Start) { 02466 const ObjCForCollectionStmt *FS = 02467 dyn_cast_or_null<ObjCForCollectionStmt>(level3); 02468 if (FS && FS->getCollection()->IgnoreParens() == s2Start && 02469 s2End == FS->getElement()) { 02470 PieceI->setEndLocation(PieceNextI->getEndLocation()); 02471 path.erase(NextI); 02472 hasChanges = true; 02473 continue; 02474 } 02475 } 02476 02477 // No changes at this index? Move to the next one. 02478 ++I; 02479 } 02480 02481 if (!hasChanges) { 02482 // Adjust edges into subexpressions to make them more uniform 02483 // and aesthetically pleasing. 02484 addContextEdges(path, SM, PM, LC); 02485 // Remove "cyclical" edges that include one or more context edges. 02486 removeContextCycles(path, SM, PM); 02487 // Hoist edges originating from branch conditions to branches 02488 // for simple branches. 02489 simplifySimpleBranches(path); 02490 // Remove any puny edges left over after primary optimization pass. 02491 removePunyEdges(path, SM, PM); 02492 // Remove identical events. 02493 removeIdenticalEvents(path); 02494 } 02495 02496 return hasChanges; 02497 } 02498 02499 /// Drop the very first edge in a path, which should be a function entry edge. 02500 /// 02501 /// If the first edge is not a function entry edge (say, because the first 02502 /// statement had an invalid source location), this function does nothing. 02503 // FIXME: We should just generate invalid edges anyway and have the optimizer 02504 // deal with them. 02505 static void dropFunctionEntryEdge(PathPieces &Path, 02506 LocationContextMap &LCM, 02507 SourceManager &SM) { 02508 const PathDiagnosticControlFlowPiece *FirstEdge = 02509 dyn_cast<PathDiagnosticControlFlowPiece>(Path.front()); 02510 if (!FirstEdge) 02511 return; 02512 02513 const Decl *D = LCM[&Path]->getDecl(); 02514 PathDiagnosticLocation EntryLoc = PathDiagnosticLocation::createBegin(D, SM); 02515 if (FirstEdge->getStartLocation() != EntryLoc) 02516 return; 02517 02518 Path.pop_front(); 02519 } 02520 02521 02522 //===----------------------------------------------------------------------===// 02523 // Methods for BugType and subclasses. 02524 //===----------------------------------------------------------------------===// 02525 void BugType::anchor() { } 02526 02527 void BugType::FlushReports(BugReporter &BR) {} 02528 02529 void BuiltinBug::anchor() {} 02530 02531 //===----------------------------------------------------------------------===// 02532 // Methods for BugReport and subclasses. 02533 //===----------------------------------------------------------------------===// 02534 02535 void BugReport::NodeResolver::anchor() {} 02536 02537 void BugReport::addVisitor(std::unique_ptr<BugReporterVisitor> visitor) { 02538 if (!visitor) 02539 return; 02540 02541 llvm::FoldingSetNodeID ID; 02542 visitor->Profile(ID); 02543 void *InsertPos; 02544 02545 if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) 02546 return; 02547 02548 CallbacksSet.InsertNode(visitor.get(), InsertPos); 02549 Callbacks.push_back(std::move(visitor)); 02550 ++ConfigurationChangeToken; 02551 } 02552 02553 BugReport::~BugReport() { 02554 while (!interestingSymbols.empty()) { 02555 popInterestingSymbolsAndRegions(); 02556 } 02557 } 02558 02559 const Decl *BugReport::getDeclWithIssue() const { 02560 if (DeclWithIssue) 02561 return DeclWithIssue; 02562 02563 const ExplodedNode *N = getErrorNode(); 02564 if (!N) 02565 return nullptr; 02566 02567 const LocationContext *LC = N->getLocationContext(); 02568 return LC->getCurrentStackFrame()->getDecl(); 02569 } 02570 02571 void BugReport::Profile(llvm::FoldingSetNodeID& hash) const { 02572 hash.AddPointer(&BT); 02573 hash.AddString(Description); 02574 PathDiagnosticLocation UL = getUniqueingLocation(); 02575 if (UL.isValid()) { 02576 UL.Profile(hash); 02577 } else if (Location.isValid()) { 02578 Location.Profile(hash); 02579 } else { 02580 assert(ErrorNode); 02581 hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode)); 02582 } 02583 02584 for (SmallVectorImpl<SourceRange>::const_iterator I = 02585 Ranges.begin(), E = Ranges.end(); I != E; ++I) { 02586 const SourceRange range = *I; 02587 if (!range.isValid()) 02588 continue; 02589 hash.AddInteger(range.getBegin().getRawEncoding()); 02590 hash.AddInteger(range.getEnd().getRawEncoding()); 02591 } 02592 } 02593 02594 void BugReport::markInteresting(SymbolRef sym) { 02595 if (!sym) 02596 return; 02597 02598 // If the symbol wasn't already in our set, note a configuration change. 02599 if (getInterestingSymbols().insert(sym).second) 02600 ++ConfigurationChangeToken; 02601 02602 if (const SymbolMetadata *meta = dyn_cast<SymbolMetadata>(sym)) 02603 getInterestingRegions().insert(meta->getRegion()); 02604 } 02605 02606 void BugReport::markInteresting(const MemRegion *R) { 02607 if (!R) 02608 return; 02609 02610 // If the base region wasn't already in our set, note a configuration change. 02611 R = R->getBaseRegion(); 02612 if (getInterestingRegions().insert(R).second) 02613 ++ConfigurationChangeToken; 02614 02615 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 02616 getInterestingSymbols().insert(SR->getSymbol()); 02617 } 02618 02619 void BugReport::markInteresting(SVal V) { 02620 markInteresting(V.getAsRegion()); 02621 markInteresting(V.getAsSymbol()); 02622 } 02623 02624 void BugReport::markInteresting(const LocationContext *LC) { 02625 if (!LC) 02626 return; 02627 InterestingLocationContexts.insert(LC); 02628 } 02629 02630 bool BugReport::isInteresting(SVal V) { 02631 return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol()); 02632 } 02633 02634 bool BugReport::isInteresting(SymbolRef sym) { 02635 if (!sym) 02636 return false; 02637 // We don't currently consider metadata symbols to be interesting 02638 // even if we know their region is interesting. Is that correct behavior? 02639 return getInterestingSymbols().count(sym); 02640 } 02641 02642 bool BugReport::isInteresting(const MemRegion *R) { 02643 if (!R) 02644 return false; 02645 R = R->getBaseRegion(); 02646 bool b = getInterestingRegions().count(R); 02647 if (b) 02648 return true; 02649 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 02650 return getInterestingSymbols().count(SR->getSymbol()); 02651 return false; 02652 } 02653 02654 bool BugReport::isInteresting(const LocationContext *LC) { 02655 if (!LC) 02656 return false; 02657 return InterestingLocationContexts.count(LC); 02658 } 02659 02660 void BugReport::lazyInitializeInterestingSets() { 02661 if (interestingSymbols.empty()) { 02662 interestingSymbols.push_back(new Symbols()); 02663 interestingRegions.push_back(new Regions()); 02664 } 02665 } 02666 02667 BugReport::Symbols &BugReport::getInterestingSymbols() { 02668 lazyInitializeInterestingSets(); 02669 return *interestingSymbols.back(); 02670 } 02671 02672 BugReport::Regions &BugReport::getInterestingRegions() { 02673 lazyInitializeInterestingSets(); 02674 return *interestingRegions.back(); 02675 } 02676 02677 void BugReport::pushInterestingSymbolsAndRegions() { 02678 interestingSymbols.push_back(new Symbols(getInterestingSymbols())); 02679 interestingRegions.push_back(new Regions(getInterestingRegions())); 02680 } 02681 02682 void BugReport::popInterestingSymbolsAndRegions() { 02683 delete interestingSymbols.pop_back_val(); 02684 delete interestingRegions.pop_back_val(); 02685 } 02686 02687 const Stmt *BugReport::getStmt() const { 02688 if (!ErrorNode) 02689 return nullptr; 02690 02691 ProgramPoint ProgP = ErrorNode->getLocation(); 02692 const Stmt *S = nullptr; 02693 02694 if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) { 02695 CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit(); 02696 if (BE->getBlock() == &Exit) 02697 S = GetPreviousStmt(ErrorNode); 02698 } 02699 if (!S) 02700 S = PathDiagnosticLocation::getStmt(ErrorNode); 02701 02702 return S; 02703 } 02704 02705 std::pair<BugReport::ranges_iterator, BugReport::ranges_iterator> 02706 BugReport::getRanges() { 02707 // If no custom ranges, add the range of the statement corresponding to 02708 // the error node. 02709 if (Ranges.empty()) { 02710 if (const Expr *E = dyn_cast_or_null<Expr>(getStmt())) 02711 addRange(E->getSourceRange()); 02712 else 02713 return std::make_pair(ranges_iterator(), ranges_iterator()); 02714 } 02715 02716 // User-specified absence of range info. 02717 if (Ranges.size() == 1 && !Ranges.begin()->isValid()) 02718 return std::make_pair(ranges_iterator(), ranges_iterator()); 02719 02720 return std::make_pair(Ranges.begin(), Ranges.end()); 02721 } 02722 02723 PathDiagnosticLocation BugReport::getLocation(const SourceManager &SM) const { 02724 if (ErrorNode) { 02725 assert(!Location.isValid() && 02726 "Either Location or ErrorNode should be specified but not both."); 02727 return PathDiagnosticLocation::createEndOfPath(ErrorNode, SM); 02728 } 02729 02730 assert(Location.isValid()); 02731 return Location; 02732 } 02733 02734 //===----------------------------------------------------------------------===// 02735 // Methods for BugReporter and subclasses. 02736 //===----------------------------------------------------------------------===// 02737 02738 BugReportEquivClass::~BugReportEquivClass() { } 02739 GRBugReporter::~GRBugReporter() { } 02740 BugReporterData::~BugReporterData() {} 02741 02742 ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); } 02743 02744 ProgramStateManager& 02745 GRBugReporter::getStateManager() { return Eng.getStateManager(); } 02746 02747 BugReporter::~BugReporter() { 02748 FlushReports(); 02749 02750 // Free the bug reports we are tracking. 02751 typedef std::vector<BugReportEquivClass *> ContTy; 02752 for (ContTy::iterator I = EQClassesVector.begin(), E = EQClassesVector.end(); 02753 I != E; ++I) { 02754 delete *I; 02755 } 02756 } 02757 02758 void BugReporter::FlushReports() { 02759 if (BugTypes.isEmpty()) 02760 return; 02761 02762 // First flush the warnings for each BugType. This may end up creating new 02763 // warnings and new BugTypes. 02764 // FIXME: Only NSErrorChecker needs BugType's FlushReports. 02765 // Turn NSErrorChecker into a proper checker and remove this. 02766 SmallVector<const BugType*, 16> bugTypes; 02767 for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I) 02768 bugTypes.push_back(*I); 02769 for (SmallVectorImpl<const BugType *>::iterator 02770 I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I) 02771 const_cast<BugType*>(*I)->FlushReports(*this); 02772 02773 // We need to flush reports in deterministic order to ensure the order 02774 // of the reports is consistent between runs. 02775 typedef std::vector<BugReportEquivClass *> ContVecTy; 02776 for (ContVecTy::iterator EI=EQClassesVector.begin(), EE=EQClassesVector.end(); 02777 EI != EE; ++EI){ 02778 BugReportEquivClass& EQ = **EI; 02779 FlushReport(EQ); 02780 } 02781 02782 // BugReporter owns and deletes only BugTypes created implicitly through 02783 // EmitBasicReport. 02784 // FIXME: There are leaks from checkers that assume that the BugTypes they 02785 // create will be destroyed by the BugReporter. 02786 llvm::DeleteContainerSeconds(StrBugTypes); 02787 02788 // Remove all references to the BugType objects. 02789 BugTypes = F.getEmptySet(); 02790 } 02791 02792 //===----------------------------------------------------------------------===// 02793 // PathDiagnostics generation. 02794 //===----------------------------------------------------------------------===// 02795 02796 namespace { 02797 /// A wrapper around a report graph, which contains only a single path, and its 02798 /// node maps. 02799 class ReportGraph { 02800 public: 02801 InterExplodedGraphMap BackMap; 02802 std::unique_ptr<ExplodedGraph> Graph; 02803 const ExplodedNode *ErrorNode; 02804 size_t Index; 02805 }; 02806 02807 /// A wrapper around a trimmed graph and its node maps. 02808 class TrimmedGraph { 02809 InterExplodedGraphMap InverseMap; 02810 02811 typedef llvm::DenseMap<const ExplodedNode *, unsigned> PriorityMapTy; 02812 PriorityMapTy PriorityMap; 02813 02814 typedef std::pair<const ExplodedNode *, size_t> NodeIndexPair; 02815 SmallVector<NodeIndexPair, 32> ReportNodes; 02816 02817 std::unique_ptr<ExplodedGraph> G; 02818 02819 /// A helper class for sorting ExplodedNodes by priority. 02820 template <bool Descending> 02821 class PriorityCompare { 02822 const PriorityMapTy &PriorityMap; 02823 02824 public: 02825 PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {} 02826 02827 bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const { 02828 PriorityMapTy::const_iterator LI = PriorityMap.find(LHS); 02829 PriorityMapTy::const_iterator RI = PriorityMap.find(RHS); 02830 PriorityMapTy::const_iterator E = PriorityMap.end(); 02831 02832 if (LI == E) 02833 return Descending; 02834 if (RI == E) 02835 return !Descending; 02836 02837 return Descending ? LI->second > RI->second 02838 : LI->second < RI->second; 02839 } 02840 02841 bool operator()(const NodeIndexPair &LHS, const NodeIndexPair &RHS) const { 02842 return (*this)(LHS.first, RHS.first); 02843 } 02844 }; 02845 02846 public: 02847 TrimmedGraph(const ExplodedGraph *OriginalGraph, 02848 ArrayRef<const ExplodedNode *> Nodes); 02849 02850 bool popNextReportGraph(ReportGraph &GraphWrapper); 02851 }; 02852 } 02853 02854 TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph, 02855 ArrayRef<const ExplodedNode *> Nodes) { 02856 // The trimmed graph is created in the body of the constructor to ensure 02857 // that the DenseMaps have been initialized already. 02858 InterExplodedGraphMap ForwardMap; 02859 G = OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap); 02860 02861 // Find the (first) error node in the trimmed graph. We just need to consult 02862 // the node map which maps from nodes in the original graph to nodes 02863 // in the new graph. 02864 llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes; 02865 02866 for (unsigned i = 0, count = Nodes.size(); i < count; ++i) { 02867 if (const ExplodedNode *NewNode = ForwardMap.lookup(Nodes[i])) { 02868 ReportNodes.push_back(std::make_pair(NewNode, i)); 02869 RemainingNodes.insert(NewNode); 02870 } 02871 } 02872 02873 assert(!RemainingNodes.empty() && "No error node found in the trimmed graph"); 02874 02875 // Perform a forward BFS to find all the shortest paths. 02876 std::queue<const ExplodedNode *> WS; 02877 02878 assert(G->num_roots() == 1); 02879 WS.push(*G->roots_begin()); 02880 unsigned Priority = 0; 02881 02882 while (!WS.empty()) { 02883 const ExplodedNode *Node = WS.front(); 02884 WS.pop(); 02885 02886 PriorityMapTy::iterator PriorityEntry; 02887 bool IsNew; 02888 std::tie(PriorityEntry, IsNew) = 02889 PriorityMap.insert(std::make_pair(Node, Priority)); 02890 ++Priority; 02891 02892 if (!IsNew) { 02893 assert(PriorityEntry->second <= Priority); 02894 continue; 02895 } 02896 02897 if (RemainingNodes.erase(Node)) 02898 if (RemainingNodes.empty()) 02899 break; 02900 02901 for (ExplodedNode::const_pred_iterator I = Node->succ_begin(), 02902 E = Node->succ_end(); 02903 I != E; ++I) 02904 WS.push(*I); 02905 } 02906 02907 // Sort the error paths from longest to shortest. 02908 std::sort(ReportNodes.begin(), ReportNodes.end(), 02909 PriorityCompare<true>(PriorityMap)); 02910 } 02911 02912 bool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) { 02913 if (ReportNodes.empty()) 02914 return false; 02915 02916 const ExplodedNode *OrigN; 02917 std::tie(OrigN, GraphWrapper.Index) = ReportNodes.pop_back_val(); 02918 assert(PriorityMap.find(OrigN) != PriorityMap.end() && 02919 "error node not accessible from root"); 02920 02921 // Create a new graph with a single path. This is the graph 02922 // that will be returned to the caller. 02923 auto GNew = llvm::make_unique<ExplodedGraph>(); 02924 GraphWrapper.BackMap.clear(); 02925 02926 // Now walk from the error node up the BFS path, always taking the 02927 // predeccessor with the lowest number. 02928 ExplodedNode *Succ = nullptr; 02929 while (true) { 02930 // Create the equivalent node in the new graph with the same state 02931 // and location. 02932 ExplodedNode *NewN = GNew->getNode(OrigN->getLocation(), OrigN->getState(), 02933 OrigN->isSink()); 02934 02935 // Store the mapping to the original node. 02936 InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN); 02937 assert(IMitr != InverseMap.end() && "No mapping to original node."); 02938 GraphWrapper.BackMap[NewN] = IMitr->second; 02939 02940 // Link up the new node with the previous node. 02941 if (Succ) 02942 Succ->addPredecessor(NewN, *GNew); 02943 else 02944 GraphWrapper.ErrorNode = NewN; 02945 02946 Succ = NewN; 02947 02948 // Are we at the final node? 02949 if (OrigN->pred_empty()) { 02950 GNew->addRoot(NewN); 02951 break; 02952 } 02953 02954 // Find the next predeccessor node. We choose the node that is marked 02955 // with the lowest BFS number. 02956 OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(), 02957 PriorityCompare<false>(PriorityMap)); 02958 } 02959 02960 GraphWrapper.Graph = std::move(GNew); 02961 02962 return true; 02963 } 02964 02965 02966 /// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object 02967 /// and collapses PathDiagosticPieces that are expanded by macros. 02968 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) { 02969 typedef std::vector<std::pair<IntrusiveRefCntPtr<PathDiagnosticMacroPiece>, 02970 SourceLocation> > MacroStackTy; 02971 02972 typedef std::vector<IntrusiveRefCntPtr<PathDiagnosticPiece> > 02973 PiecesTy; 02974 02975 MacroStackTy MacroStack; 02976 PiecesTy Pieces; 02977 02978 for (PathPieces::const_iterator I = path.begin(), E = path.end(); 02979 I!=E; ++I) { 02980 02981 PathDiagnosticPiece *piece = I->get(); 02982 02983 // Recursively compact calls. 02984 if (PathDiagnosticCallPiece *call=dyn_cast<PathDiagnosticCallPiece>(piece)){ 02985 CompactPathDiagnostic(call->path, SM); 02986 } 02987 02988 // Get the location of the PathDiagnosticPiece. 02989 const FullSourceLoc Loc = piece->getLocation().asLocation(); 02990 02991 // Determine the instantiation location, which is the location we group 02992 // related PathDiagnosticPieces. 02993 SourceLocation InstantiationLoc = Loc.isMacroID() ? 02994 SM.getExpansionLoc(Loc) : 02995 SourceLocation(); 02996 02997 if (Loc.isFileID()) { 02998 MacroStack.clear(); 02999 Pieces.push_back(piece); 03000 continue; 03001 } 03002 03003 assert(Loc.isMacroID()); 03004 03005 // Is the PathDiagnosticPiece within the same macro group? 03006 if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) { 03007 MacroStack.back().first->subPieces.push_back(piece); 03008 continue; 03009 } 03010 03011 // We aren't in the same group. Are we descending into a new macro 03012 // or are part of an old one? 03013 IntrusiveRefCntPtr<PathDiagnosticMacroPiece> MacroGroup; 03014 03015 SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ? 03016 SM.getExpansionLoc(Loc) : 03017 SourceLocation(); 03018 03019 // Walk the entire macro stack. 03020 while (!MacroStack.empty()) { 03021 if (InstantiationLoc == MacroStack.back().second) { 03022 MacroGroup = MacroStack.back().first; 03023 break; 03024 } 03025 03026 if (ParentInstantiationLoc == MacroStack.back().second) { 03027 MacroGroup = MacroStack.back().first; 03028 break; 03029 } 03030 03031 MacroStack.pop_back(); 03032 } 03033 03034 if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) { 03035 // Create a new macro group and add it to the stack. 03036 PathDiagnosticMacroPiece *NewGroup = 03037 new PathDiagnosticMacroPiece( 03038 PathDiagnosticLocation::createSingleLocation(piece->getLocation())); 03039 03040 if (MacroGroup) 03041 MacroGroup->subPieces.push_back(NewGroup); 03042 else { 03043 assert(InstantiationLoc.isFileID()); 03044 Pieces.push_back(NewGroup); 03045 } 03046 03047 MacroGroup = NewGroup; 03048 MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc)); 03049 } 03050 03051 // Finally, add the PathDiagnosticPiece to the group. 03052 MacroGroup->subPieces.push_back(piece); 03053 } 03054 03055 // Now take the pieces and construct a new PathDiagnostic. 03056 path.clear(); 03057 03058 for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I) 03059 path.push_back(*I); 03060 } 03061 03062 bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD, 03063 PathDiagnosticConsumer &PC, 03064 ArrayRef<BugReport *> &bugReports) { 03065 assert(!bugReports.empty()); 03066 03067 bool HasValid = false; 03068 bool HasInvalid = false; 03069 SmallVector<const ExplodedNode *, 32> errorNodes; 03070 for (ArrayRef<BugReport*>::iterator I = bugReports.begin(), 03071 E = bugReports.end(); I != E; ++I) { 03072 if ((*I)->isValid()) { 03073 HasValid = true; 03074 errorNodes.push_back((*I)->getErrorNode()); 03075 } else { 03076 // Keep the errorNodes list in sync with the bugReports list. 03077 HasInvalid = true; 03078 errorNodes.push_back(nullptr); 03079 } 03080 } 03081 03082 // If all the reports have been marked invalid by a previous path generation, 03083 // we're done. 03084 if (!HasValid) 03085 return false; 03086 03087 typedef PathDiagnosticConsumer::PathGenerationScheme PathGenerationScheme; 03088 PathGenerationScheme ActiveScheme = PC.getGenerationScheme(); 03089 03090 if (ActiveScheme == PathDiagnosticConsumer::Extensive) { 03091 AnalyzerOptions &options = getAnalyzerOptions(); 03092 if (options.getBooleanOption("path-diagnostics-alternate", true)) { 03093 ActiveScheme = PathDiagnosticConsumer::AlternateExtensive; 03094 } 03095 } 03096 03097 TrimmedGraph TrimG(&getGraph(), errorNodes); 03098 ReportGraph ErrorGraph; 03099 03100 while (TrimG.popNextReportGraph(ErrorGraph)) { 03101 // Find the BugReport with the original location. 03102 assert(ErrorGraph.Index < bugReports.size()); 03103 BugReport *R = bugReports[ErrorGraph.Index]; 03104 assert(R && "No original report found for sliced graph."); 03105 assert(R->isValid() && "Report selected by trimmed graph marked invalid."); 03106 03107 // Start building the path diagnostic... 03108 PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, &PC); 03109 const ExplodedNode *N = ErrorGraph.ErrorNode; 03110 03111 // Register additional node visitors. 03112 R->addVisitor(llvm::make_unique<NilReceiverBRVisitor>()); 03113 R->addVisitor(llvm::make_unique<ConditionBRVisitor>()); 03114 R->addVisitor(llvm::make_unique<LikelyFalsePositiveSuppressionBRVisitor>()); 03115 03116 BugReport::VisitorList visitors; 03117 unsigned origReportConfigToken, finalReportConfigToken; 03118 LocationContextMap LCM; 03119 03120 // While generating diagnostics, it's possible the visitors will decide 03121 // new symbols and regions are interesting, or add other visitors based on 03122 // the information they find. If they do, we need to regenerate the path 03123 // based on our new report configuration. 03124 do { 03125 // Get a clean copy of all the visitors. 03126 for (BugReport::visitor_iterator I = R->visitor_begin(), 03127 E = R->visitor_end(); I != E; ++I) 03128 visitors.push_back((*I)->clone()); 03129 03130 // Clear out the active path from any previous work. 03131 PD.resetPath(); 03132 origReportConfigToken = R->getConfigurationChangeToken(); 03133 03134 // Generate the very last diagnostic piece - the piece is visible before 03135 // the trace is expanded. 03136 std::unique_ptr<PathDiagnosticPiece> LastPiece; 03137 for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end(); 03138 I != E; ++I) { 03139 if (std::unique_ptr<PathDiagnosticPiece> Piece = 03140 (*I)->getEndPath(PDB, N, *R)) { 03141 assert (!LastPiece && 03142 "There can only be one final piece in a diagnostic."); 03143 LastPiece = std::move(Piece); 03144 } 03145 } 03146 03147 if (ActiveScheme != PathDiagnosticConsumer::None) { 03148 if (!LastPiece) 03149 LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R); 03150 assert(LastPiece); 03151 PD.setEndOfPath(std::move(LastPiece)); 03152 } 03153 03154 // Make sure we get a clean location context map so we don't 03155 // hold onto old mappings. 03156 LCM.clear(); 03157 03158 switch (ActiveScheme) { 03159 case PathDiagnosticConsumer::AlternateExtensive: 03160 GenerateAlternateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors); 03161 break; 03162 case PathDiagnosticConsumer::Extensive: 03163 GenerateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors); 03164 break; 03165 case PathDiagnosticConsumer::Minimal: 03166 GenerateMinimalPathDiagnostic(PD, PDB, N, LCM, visitors); 03167 break; 03168 case PathDiagnosticConsumer::None: 03169 GenerateVisitorsOnlyPathDiagnostic(PD, PDB, N, visitors); 03170 break; 03171 } 03172 03173 // Clean up the visitors we used. 03174 visitors.clear(); 03175 03176 // Did anything change while generating this path? 03177 finalReportConfigToken = R->getConfigurationChangeToken(); 03178 } while (finalReportConfigToken != origReportConfigToken); 03179 03180 if (!R->isValid()) 03181 continue; 03182 03183 // Finally, prune the diagnostic path of uninteresting stuff. 03184 if (!PD.path.empty()) { 03185 if (R->shouldPrunePath() && getAnalyzerOptions().shouldPrunePaths()) { 03186 bool stillHasNotes = removeUnneededCalls(PD.getMutablePieces(), R, LCM); 03187 assert(stillHasNotes); 03188 (void)stillHasNotes; 03189 } 03190 03191 // Redirect all call pieces to have valid locations. 03192 adjustCallLocations(PD.getMutablePieces()); 03193 removePiecesWithInvalidLocations(PD.getMutablePieces()); 03194 03195 if (ActiveScheme == PathDiagnosticConsumer::AlternateExtensive) { 03196 SourceManager &SM = getSourceManager(); 03197 03198 // Reduce the number of edges from a very conservative set 03199 // to an aesthetically pleasing subset that conveys the 03200 // necessary information. 03201 OptimizedCallsSet OCS; 03202 while (optimizeEdges(PD.getMutablePieces(), SM, OCS, LCM)) {} 03203 03204 // Drop the very first function-entry edge. It's not really necessary 03205 // for top-level functions. 03206 dropFunctionEntryEdge(PD.getMutablePieces(), LCM, SM); 03207 } 03208 03209 // Remove messages that are basically the same, and edges that may not 03210 // make sense. 03211 // We have to do this after edge optimization in the Extensive mode. 03212 removeRedundantMsgs(PD.getMutablePieces()); 03213 removeEdgesToDefaultInitializers(PD.getMutablePieces()); 03214 } 03215 03216 // We found a report and didn't suppress it. 03217 return true; 03218 } 03219 03220 // We suppressed all the reports in this equivalence class. 03221 assert(!HasInvalid && "Inconsistent suppression"); 03222 (void)HasInvalid; 03223 return false; 03224 } 03225 03226 void BugReporter::Register(BugType *BT) { 03227 BugTypes = F.add(BugTypes, BT); 03228 } 03229 03230 void BugReporter::emitReport(BugReport* R) { 03231 // To guarantee memory release. 03232 std::unique_ptr<BugReport> UniqueR(R); 03233 03234 if (const ExplodedNode *E = R->getErrorNode()) { 03235 const AnalysisDeclContext *DeclCtx = 03236 E->getLocationContext()->getAnalysisDeclContext(); 03237 // The source of autosynthesized body can be handcrafted AST or a model 03238 // file. The locations from handcrafted ASTs have no valid source locations 03239 // and have to be discarded. Locations from model files should be preserved 03240 // for processing and reporting. 03241 if (DeclCtx->isBodyAutosynthesized() && 03242 !DeclCtx->isBodyAutosynthesizedFromModelFile()) 03243 return; 03244 } 03245 03246 bool ValidSourceLoc = R->getLocation(getSourceManager()).isValid(); 03247 assert(ValidSourceLoc); 03248 // If we mess up in a release build, we'd still prefer to just drop the bug 03249 // instead of trying to go on. 03250 if (!ValidSourceLoc) 03251 return; 03252 03253 // Compute the bug report's hash to determine its equivalence class. 03254 llvm::FoldingSetNodeID ID; 03255 R->Profile(ID); 03256 03257 // Lookup the equivance class. If there isn't one, create it. 03258 BugType& BT = R->getBugType(); 03259 Register(&BT); 03260 void *InsertPos; 03261 BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos); 03262 03263 if (!EQ) { 03264 EQ = new BugReportEquivClass(std::move(UniqueR)); 03265 EQClasses.InsertNode(EQ, InsertPos); 03266 EQClassesVector.push_back(EQ); 03267 } else 03268 EQ->AddReport(std::move(UniqueR)); 03269 } 03270 03271 03272 //===----------------------------------------------------------------------===// 03273 // Emitting reports in equivalence classes. 03274 //===----------------------------------------------------------------------===// 03275 03276 namespace { 03277 struct FRIEC_WLItem { 03278 const ExplodedNode *N; 03279 ExplodedNode::const_succ_iterator I, E; 03280 03281 FRIEC_WLItem(const ExplodedNode *n) 03282 : N(n), I(N->succ_begin()), E(N->succ_end()) {} 03283 }; 03284 } 03285 03286 static BugReport * 03287 FindReportInEquivalenceClass(BugReportEquivClass& EQ, 03288 SmallVectorImpl<BugReport*> &bugReports) { 03289 03290 BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end(); 03291 assert(I != E); 03292 BugType& BT = I->getBugType(); 03293 03294 // If we don't need to suppress any of the nodes because they are 03295 // post-dominated by a sink, simply add all the nodes in the equivalence class 03296 // to 'Nodes'. Any of the reports will serve as a "representative" report. 03297 if (!BT.isSuppressOnSink()) { 03298 BugReport *R = I; 03299 for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) { 03300 const ExplodedNode *N = I->getErrorNode(); 03301 if (N) { 03302 R = I; 03303 bugReports.push_back(R); 03304 } 03305 } 03306 return R; 03307 } 03308 03309 // For bug reports that should be suppressed when all paths are post-dominated 03310 // by a sink node, iterate through the reports in the equivalence class 03311 // until we find one that isn't post-dominated (if one exists). We use a 03312 // DFS traversal of the ExplodedGraph to find a non-sink node. We could write 03313 // this as a recursive function, but we don't want to risk blowing out the 03314 // stack for very long paths. 03315 BugReport *exampleReport = nullptr; 03316 03317 for (; I != E; ++I) { 03318 const ExplodedNode *errorNode = I->getErrorNode(); 03319 03320 if (!errorNode) 03321 continue; 03322 if (errorNode->isSink()) { 03323 llvm_unreachable( 03324 "BugType::isSuppressSink() should not be 'true' for sink end nodes"); 03325 } 03326 // No successors? By definition this nodes isn't post-dominated by a sink. 03327 if (errorNode->succ_empty()) { 03328 bugReports.push_back(I); 03329 if (!exampleReport) 03330 exampleReport = I; 03331 continue; 03332 } 03333 03334 // At this point we know that 'N' is not a sink and it has at least one 03335 // successor. Use a DFS worklist to find a non-sink end-of-path node. 03336 typedef FRIEC_WLItem WLItem; 03337 typedef SmallVector<WLItem, 10> DFSWorkList; 03338 llvm::DenseMap<const ExplodedNode *, unsigned> Visited; 03339 03340 DFSWorkList WL; 03341 WL.push_back(errorNode); 03342 Visited[errorNode] = 1; 03343 03344 while (!WL.empty()) { 03345 WLItem &WI = WL.back(); 03346 assert(!WI.N->succ_empty()); 03347 03348 for (; WI.I != WI.E; ++WI.I) { 03349 const ExplodedNode *Succ = *WI.I; 03350 // End-of-path node? 03351 if (Succ->succ_empty()) { 03352 // If we found an end-of-path node that is not a sink. 03353 if (!Succ->isSink()) { 03354 bugReports.push_back(I); 03355 if (!exampleReport) 03356 exampleReport = I; 03357 WL.clear(); 03358 break; 03359 } 03360 // Found a sink? Continue on to the next successor. 03361 continue; 03362 } 03363 // Mark the successor as visited. If it hasn't been explored, 03364 // enqueue it to the DFS worklist. 03365 unsigned &mark = Visited[Succ]; 03366 if (!mark) { 03367 mark = 1; 03368 WL.push_back(Succ); 03369 break; 03370 } 03371 } 03372 03373 // The worklist may have been cleared at this point. First 03374 // check if it is empty before checking the last item. 03375 if (!WL.empty() && &WL.back() == &WI) 03376 WL.pop_back(); 03377 } 03378 } 03379 03380 // ExampleReport will be NULL if all the nodes in the equivalence class 03381 // were post-dominated by sinks. 03382 return exampleReport; 03383 } 03384 03385 void BugReporter::FlushReport(BugReportEquivClass& EQ) { 03386 SmallVector<BugReport*, 10> bugReports; 03387 BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports); 03388 if (exampleReport) { 03389 for (PathDiagnosticConsumer *PDC : getPathDiagnosticConsumers()) { 03390 FlushReport(exampleReport, *PDC, bugReports); 03391 } 03392 } 03393 } 03394 03395 void BugReporter::FlushReport(BugReport *exampleReport, 03396 PathDiagnosticConsumer &PD, 03397 ArrayRef<BugReport*> bugReports) { 03398 03399 // FIXME: Make sure we use the 'R' for the path that was actually used. 03400 // Probably doesn't make a difference in practice. 03401 BugType& BT = exampleReport->getBugType(); 03402 03403 std::unique_ptr<PathDiagnostic> D(new PathDiagnostic( 03404 exampleReport->getBugType().getCheckName(), 03405 exampleReport->getDeclWithIssue(), exampleReport->getBugType().getName(), 03406 exampleReport->getDescription(), 03407 exampleReport->getShortDescription(/*Fallback=*/false), BT.getCategory(), 03408 exampleReport->getUniqueingLocation(), 03409 exampleReport->getUniqueingDecl())); 03410 03411 MaxBugClassSize = std::max(bugReports.size(), 03412 static_cast<size_t>(MaxBugClassSize)); 03413 03414 // Generate the full path diagnostic, using the generation scheme 03415 // specified by the PathDiagnosticConsumer. Note that we have to generate 03416 // path diagnostics even for consumers which do not support paths, because 03417 // the BugReporterVisitors may mark this bug as a false positive. 03418 if (!bugReports.empty()) 03419 if (!generatePathDiagnostic(*D.get(), PD, bugReports)) 03420 return; 03421 03422 MaxValidBugClassSize = std::max(bugReports.size(), 03423 static_cast<size_t>(MaxValidBugClassSize)); 03424 03425 // Examine the report and see if the last piece is in a header. Reset the 03426 // report location to the last piece in the main source file. 03427 AnalyzerOptions& Opts = getAnalyzerOptions(); 03428 if (Opts.shouldReportIssuesInMainSourceFile() && !Opts.AnalyzeAll) 03429 D->resetDiagnosticLocationToMainFile(); 03430 03431 // If the path is empty, generate a single step path with the location 03432 // of the issue. 03433 if (D->path.empty()) { 03434 PathDiagnosticLocation L = exampleReport->getLocation(getSourceManager()); 03435 auto piece = llvm::make_unique<PathDiagnosticEventPiece>( 03436 L, exampleReport->getDescription()); 03437 BugReport::ranges_iterator Beg, End; 03438 std::tie(Beg, End) = exampleReport->getRanges(); 03439 for ( ; Beg != End; ++Beg) 03440 piece->addRange(*Beg); 03441 D->setEndOfPath(std::move(piece)); 03442 } 03443 03444 // Get the meta data. 03445 const BugReport::ExtraTextList &Meta = exampleReport->getExtraText(); 03446 for (BugReport::ExtraTextList::const_iterator i = Meta.begin(), 03447 e = Meta.end(); i != e; ++i) { 03448 D->addMeta(*i); 03449 } 03450 03451 PD.HandlePathDiagnostic(std::move(D)); 03452 } 03453 03454 void BugReporter::EmitBasicReport(const Decl *DeclWithIssue, 03455 const CheckerBase *Checker, 03456 StringRef Name, StringRef Category, 03457 StringRef Str, PathDiagnosticLocation Loc, 03458 ArrayRef<SourceRange> Ranges) { 03459 EmitBasicReport(DeclWithIssue, Checker->getCheckName(), Name, Category, Str, 03460 Loc, Ranges); 03461 } 03462 void BugReporter::EmitBasicReport(const Decl *DeclWithIssue, 03463 CheckName CheckName, 03464 StringRef name, StringRef category, 03465 StringRef str, PathDiagnosticLocation Loc, 03466 ArrayRef<SourceRange> Ranges) { 03467 03468 // 'BT' is owned by BugReporter. 03469 BugType *BT = getBugTypeForName(CheckName, name, category); 03470 BugReport *R = new BugReport(*BT, str, Loc); 03471 R->setDeclWithIssue(DeclWithIssue); 03472 for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end(); 03473 I != E; ++I) 03474 R->addRange(*I); 03475 emitReport(R); 03476 } 03477 03478 BugType *BugReporter::getBugTypeForName(CheckName CheckName, StringRef name, 03479 StringRef category) { 03480 SmallString<136> fullDesc; 03481 llvm::raw_svector_ostream(fullDesc) << CheckName.getName() << ":" << name 03482 << ":" << category; 03483 llvm::StringMapEntry<BugType *> & 03484 entry = StrBugTypes.GetOrCreateValue(fullDesc); 03485 BugType *BT = entry.getValue(); 03486 if (!BT) { 03487 BT = new BugType(CheckName, name, category); 03488 entry.setValue(BT); 03489 } 03490 return BT; 03491 } 03492 03493 LLVM_DUMP_METHOD void PathPieces::dump() const { 03494 unsigned index = 0; 03495 for (PathPieces::const_iterator I = begin(), E = end(); I != E; ++I) { 03496 llvm::errs() << "[" << index++ << "] "; 03497 (*I)->dump(); 03498 llvm::errs() << "\n"; 03499 } 03500 } 03501 03502 void PathDiagnosticCallPiece::dump() const { 03503 llvm::errs() << "CALL\n--------------\n"; 03504 03505 if (const Stmt *SLoc = getLocStmt(getLocation())) 03506 SLoc->dump(); 03507 else if (const NamedDecl *ND = dyn_cast<NamedDecl>(getCallee())) 03508 llvm::errs() << *ND << "\n"; 03509 else 03510 getLocation().dump(); 03511 } 03512 03513 void PathDiagnosticEventPiece::dump() const { 03514 llvm::errs() << "EVENT\n--------------\n"; 03515 llvm::errs() << getString() << "\n"; 03516 llvm::errs() << " ---- at ----\n"; 03517 getLocation().dump(); 03518 } 03519 03520 void PathDiagnosticControlFlowPiece::dump() const { 03521 llvm::errs() << "CONTROL\n--------------\n"; 03522 getStartLocation().dump(); 03523 llvm::errs() << " ---- to ----\n"; 03524 getEndLocation().dump(); 03525 } 03526 03527 void PathDiagnosticMacroPiece::dump() const { 03528 llvm::errs() << "MACRO\n--------------\n"; 03529 // FIXME: Print which macro is being invoked. 03530 } 03531 03532 void PathDiagnosticLocation::dump() const { 03533 if (!isValid()) { 03534 llvm::errs() << "<INVALID>\n"; 03535 return; 03536 } 03537 03538 switch (K) { 03539 case RangeK: 03540 // FIXME: actually print the range. 03541 llvm::errs() << "<range>\n"; 03542 break; 03543 case SingleLocK: 03544 asLocation().dump(); 03545 llvm::errs() << "\n"; 03546 break; 03547 case StmtK: 03548 if (S) 03549 S->dump(); 03550 else 03551 llvm::errs() << "<NULL STMT>\n"; 03552 break; 03553 case DeclK: 03554 if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D)) 03555 llvm::errs() << *ND << "\n"; 03556 else if (isa<BlockDecl>(D)) 03557 // FIXME: Make this nicer. 03558 llvm::errs() << "<block>\n"; 03559 else if (D) 03560 llvm::errs() << "<unknown decl>\n"; 03561 else 03562 llvm::errs() << "<NULL DECL>\n"; 03563 break; 03564 } 03565 }