clang API Documentation

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