contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/BugReporter.cpp

   1 // BugReporter.cpp - Generate PathDiagnostics for Bugs ------------*- C++ -*--//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defines BugReporter, a utility class for generating
  11 //  PathDiagnostics.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  16 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  18 #include "clang/AST/ASTContext.h"
  19 #include "clang/Analysis/CFG.h"
  20 #include "clang/AST/DeclObjC.h"
  21 #include "clang/AST/Expr.h"
  22 #include "clang/AST/ParentMap.h"
  23 #include "clang/AST/StmtObjC.h"
  24 #include "clang/Basic/SourceManager.h"
  25 #include "clang/Analysis/ProgramPoint.h"
  26 #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include "llvm/ADT/DenseMap.h"
  29 #include "llvm/ADT/SmallString.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 #include "llvm/ADT/OwningPtr.h"
  32 #include "llvm/ADT/IntrusiveRefCntPtr.h"
  33 #include <queue>
  34
  35 using namespace clang;
  36 using namespace ento;
  37
  38 BugReporterVisitor::~BugReporterVisitor() {}
  39
  40 void BugReporterContext::anchor() {}
  41
  42 //===----------------------------------------------------------------------===//
  43 // Helper routines for walking the ExplodedGraph and fetching statements.
  44 //===----------------------------------------------------------------------===//
  45
  46 static inline const Stmt *GetStmt(const ProgramPoint &P) {
  47   if (const StmtPoint* SP = dyn_cast<StmtPoint>(&P))
  48     return SP->getStmt();
  49   else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P))
  50     return BE->getSrc()->getTerminator();
  51
  52   return 0;
  53 }
  54
  55 static inline const ExplodedNode*
  56 GetPredecessorNode(const ExplodedNode *N) {
  57   return N->pred_empty() ? NULL : *(N->pred_begin());
  58 }
  59
  60 static inline const ExplodedNode*
  61 GetSuccessorNode(const ExplodedNode *N) {
  62   return N->succ_empty() ? NULL : *(N->succ_begin());
  63 }
  64
  65 static const Stmt *GetPreviousStmt(const ExplodedNode *N) {
  66   for (N = GetPredecessorNode(N); N; N = GetPredecessorNode(N))
  67     if (const Stmt *S = GetStmt(N->getLocation()))
  68       return S;
  69
  70   return 0;
  71 }
  72
  73 static const Stmt *GetNextStmt(const ExplodedNode *N) {
  74   for (N = GetSuccessorNode(N); N; N = GetSuccessorNode(N))
  75     if (const Stmt *S = GetStmt(N->getLocation())) {
  76       // Check if the statement is '?' or '&&'/'||'.  These are "merges",
  77       // not actual statement points.
  78       switch (S->getStmtClass()) {
  79         case Stmt::ChooseExprClass:
  80         case Stmt::BinaryConditionalOperatorClass: continue;
  81         case Stmt::ConditionalOperatorClass: continue;
  82         case Stmt::BinaryOperatorClass: {
  83           BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode();
  84           if (Op == BO_LAnd || Op == BO_LOr)
  85             continue;
  86           break;
  87         }
  88         default:
  89           break;
  90       }
  91       return S;
  92     }
  93
  94   return 0;
  95 }
  96
  97 static inline const Stmt*
  98 GetCurrentOrPreviousStmt(const ExplodedNode *N) {
  99   if (const Stmt *S = GetStmt(N->getLocation()))
 100     return S;
 101
 102   return GetPreviousStmt(N);
 103 }
 104
 105 static inline const Stmt*
 106 GetCurrentOrNextStmt(const ExplodedNode *N) {
 107   if (const Stmt *S = GetStmt(N->getLocation()))
 108     return S;
 109
 110   return GetNextStmt(N);
 111 }
 112
 113 //===----------------------------------------------------------------------===//
 114 // Diagnostic cleanup.
 115 //===----------------------------------------------------------------------===//
 116
 117 /// Recursively scan through a path and prune out calls and macros pieces
 118 /// that aren't needed.  Return true if afterwards the path contains
 119 /// "interesting stuff" which means it should be pruned from the parent path.
 120 static bool RemoveUneededCalls(PathPieces &pieces) {
 121   bool containsSomethingInteresting = false;
 122   const unsigned N = pieces.size();
 123
 124   for (unsigned i = 0 ; i < N ; ++i) {
 125     // Remove the front piece from the path.  If it is still something we
 126     // want to keep once we are done, we will push it back on the end.
 127     IntrusiveRefCntPtr<PathDiagnosticPiece> piece(pieces.front());
 128     pieces.pop_front();
 129
 130     switch (piece->getKind()) {
 131       case PathDiagnosticPiece::Call: {
 132         PathDiagnosticCallPiece *call = cast<PathDiagnosticCallPiece>(piece);
 133         // Recursively clean out the subclass.  Keep this call around if
 134         // it contains any informative diagnostics.
 135         if (!RemoveUneededCalls(call->path))
 136           continue;
 137         containsSomethingInteresting = true;
 138         break;
 139       }
 140       case PathDiagnosticPiece::Macro: {
 141         PathDiagnosticMacroPiece *macro = cast<PathDiagnosticMacroPiece>(piece);
 142         if (!RemoveUneededCalls(macro->subPieces))
 143           continue;
 144         containsSomethingInteresting = true;
 145         break;
 146       }
 147       case PathDiagnosticPiece::Event: {
 148         PathDiagnosticEventPiece *event = cast<PathDiagnosticEventPiece>(piece);
 149         // We never throw away an event, but we do throw it away wholesale
 150         // as part of a path if we throw the entire path away.
 151         if (event->isPrunable())
 152           continue;
 153         containsSomethingInteresting = true;
 154         break;
 155       }
 156       case PathDiagnosticPiece::ControlFlow:
 157         break;
 158     }
 159
 160     pieces.push_back(piece);
 161   }
 162
 163   return containsSomethingInteresting;
 164 }
 165
 166 //===----------------------------------------------------------------------===//
 167 // PathDiagnosticBuilder and its associated routines and helper objects.
 168 //===----------------------------------------------------------------------===//
 169
 170 typedef llvm::DenseMap<const ExplodedNode*,
 171 const ExplodedNode*> NodeBackMap;
 172
 173 namespace {
 174 class NodeMapClosure : public BugReport::NodeResolver {
 175   NodeBackMap& M;
 176 public:
 177   NodeMapClosure(NodeBackMap *m) : M(*m) {}
 178   ~NodeMapClosure() {}
 179
 180   const ExplodedNode *getOriginalNode(const ExplodedNode *N) {
 181     NodeBackMap::iterator I = M.find(N);
 182     return I == M.end() ? 0 : I->second;
 183   }
 184 };
 185
 186 class PathDiagnosticBuilder : public BugReporterContext {
 187   BugReport *R;
 188   PathDiagnosticConsumer *PDC;
 189   OwningPtr<ParentMap> PM;
 190   NodeMapClosure NMC;
 191 public:
 192   const LocationContext *LC;
 193
 194   PathDiagnosticBuilder(GRBugReporter &br,
 195                         BugReport *r, NodeBackMap *Backmap,
 196                         PathDiagnosticConsumer *pdc)
 197     : BugReporterContext(br),
 198       R(r), PDC(pdc), NMC(Backmap), LC(r->getErrorNode()->getLocationContext())
 199   {}
 200
 201   PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N);
 202
 203   PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os,
 204                                             const ExplodedNode *N);
 205
 206   BugReport *getBugReport() { return R; }
 207
 208   Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); }
 209
 210   ParentMap& getParentMap() { return LC->getParentMap(); }
 211
 212   const Stmt *getParent(const Stmt *S) {
 213     return getParentMap().getParent(S);
 214   }
 215
 216   virtual NodeMapClosure& getNodeResolver() { return NMC; }
 217
 218   PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S);
 219
 220   PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const {
 221     return PDC ? PDC->getGenerationScheme() : PathDiagnosticConsumer::Extensive;
 222   }
 223
 224   bool supportsLogicalOpControlFlow() const {
 225     return PDC ? PDC->supportsLogicalOpControlFlow() : true;
 226   }
 227 };
 228 } // end anonymous namespace
 229
 230 PathDiagnosticLocation
 231 PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) {
 232   if (const Stmt *S = GetNextStmt(N))
 233     return PathDiagnosticLocation(S, getSourceManager(), LC);
 234
 235   return PathDiagnosticLocation::createDeclEnd(N->getLocationContext(),
 236                                                getSourceManager());
 237 }
 238
 239 PathDiagnosticLocation
 240 PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os,
 241                                           const ExplodedNode *N) {
 242
 243   // Slow, but probably doesn't matter.
 244   if (os.str().empty())
 245     os << ' ';
 246
 247   const PathDiagnosticLocation &Loc = ExecutionContinues(N);
 248
 249   if (Loc.asStmt())
 250     os << "Execution continues on line "
 251        << getSourceManager().getExpansionLineNumber(Loc.asLocation())
 252        << '.';
 253   else {
 254     os << "Execution jumps to the end of the ";
 255     const Decl *D = N->getLocationContext()->getDecl();
 256     if (isa<ObjCMethodDecl>(D))
 257       os << "method";
 258     else if (isa<FunctionDecl>(D))
 259       os << "function";
 260     else {
 261       assert(isa<BlockDecl>(D));
 262       os << "anonymous block";
 263     }
 264     os << '.';
 265   }
 266
 267   return Loc;
 268 }
 269
 270 static bool IsNested(const Stmt *S, ParentMap &PM) {
 271   if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S)))
 272     return true;
 273
 274   const Stmt *Parent = PM.getParentIgnoreParens(S);
 275
 276   if (Parent)
 277     switch (Parent->getStmtClass()) {
 278       case Stmt::ForStmtClass:
 279       case Stmt::DoStmtClass:
 280       case Stmt::WhileStmtClass:
 281         return true;
 282       default:
 283         break;
 284     }
 285
 286   return false;
 287 }
 288
 289 PathDiagnosticLocation
 290 PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) {
 291   assert(S && "Null Stmt *passed to getEnclosingStmtLocation");
 292   ParentMap &P = getParentMap();
 293   SourceManager &SMgr = getSourceManager();
 294
 295   while (IsNested(S, P)) {
 296     const Stmt *Parent = P.getParentIgnoreParens(S);
 297
 298     if (!Parent)
 299       break;
 300
 301     switch (Parent->getStmtClass()) {
 302       case Stmt::BinaryOperatorClass: {
 303         const BinaryOperator *B = cast<BinaryOperator>(Parent);
 304         if (B->isLogicalOp())
 305           return PathDiagnosticLocation(S, SMgr, LC);
 306         break;
 307       }
 308       case Stmt::CompoundStmtClass:
 309       case Stmt::StmtExprClass:
 310         return PathDiagnosticLocation(S, SMgr, LC);
 311       case Stmt::ChooseExprClass:
 312         // Similar to '?' if we are referring to condition, just have the edge
 313         // point to the entire choose expression.
 314         if (cast<ChooseExpr>(Parent)->getCond() == S)
 315           return PathDiagnosticLocation(Parent, SMgr, LC);
 316         else
 317           return PathDiagnosticLocation(S, SMgr, LC);
 318       case Stmt::BinaryConditionalOperatorClass:
 319       case Stmt::ConditionalOperatorClass:
 320         // For '?', if we are referring to condition, just have the edge point
 321         // to the entire '?' expression.
 322         if (cast<AbstractConditionalOperator>(Parent)->getCond() == S)
 323           return PathDiagnosticLocation(Parent, SMgr, LC);
 324         else
 325           return PathDiagnosticLocation(S, SMgr, LC);
 326       case Stmt::DoStmtClass:
 327           return PathDiagnosticLocation(S, SMgr, LC);
 328       case Stmt::ForStmtClass:
 329         if (cast<ForStmt>(Parent)->getBody() == S)
 330           return PathDiagnosticLocation(S, SMgr, LC);
 331         break;
 332       case Stmt::IfStmtClass:
 333         if (cast<IfStmt>(Parent)->getCond() != S)
 334           return PathDiagnosticLocation(S, SMgr, LC);
 335         break;
 336       case Stmt::ObjCForCollectionStmtClass:
 337         if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S)
 338           return PathDiagnosticLocation(S, SMgr, LC);
 339         break;
 340       case Stmt::WhileStmtClass:
 341         if (cast<WhileStmt>(Parent)->getCond() != S)
 342           return PathDiagnosticLocation(S, SMgr, LC);
 343         break;
 344       default:
 345         break;
 346     }
 347
 348     S = Parent;
 349   }
 350
 351   assert(S && "Cannot have null Stmt for PathDiagnosticLocation");
 352
 353   // Special case: DeclStmts can appear in for statement declarations, in which
 354   //  case the ForStmt is the context.
 355   if (isa<DeclStmt>(S)) {
 356     if (const Stmt *Parent = P.getParent(S)) {
 357       switch (Parent->getStmtClass()) {
 358         case Stmt::ForStmtClass:
 359         case Stmt::ObjCForCollectionStmtClass:
 360           return PathDiagnosticLocation(Parent, SMgr, LC);
 361         default:
 362           break;
 363       }
 364     }
 365   }
 366   else if (isa<BinaryOperator>(S)) {
 367     // Special case: the binary operator represents the initialization
 368     // code in a for statement (this can happen when the variable being
 369     // initialized is an old variable.
 370     if (const ForStmt *FS =
 371           dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) {
 372       if (FS->getInit() == S)
 373         return PathDiagnosticLocation(FS, SMgr, LC);
 374     }
 375   }
 376
 377   return PathDiagnosticLocation(S, SMgr, LC);
 378 }
 379
 380 //===----------------------------------------------------------------------===//
 381 // "Minimal" path diagnostic generation algorithm.
 382 //===----------------------------------------------------------------------===//
 383 typedef std::pair<PathDiagnosticCallPiece*, const ExplodedNode*> StackDiagPair;
 384 typedef SmallVector<StackDiagPair, 6> StackDiagVector;
 385
 386 static void updateStackPiecesWithMessage(PathDiagnosticPiece *P,
 387                                          StackDiagVector &CallStack) {
 388   // If the piece contains a special message, add it to all the call
 389   // pieces on the active stack.
 390   if (PathDiagnosticEventPiece *ep =
 391         dyn_cast<PathDiagnosticEventPiece>(P)) {
 392
 393     if (ep->hasCallStackHint())
 394       for (StackDiagVector::iterator I = CallStack.begin(),
 395                                      E = CallStack.end(); I != E; ++I) {
 396         PathDiagnosticCallPiece *CP = I->first;
 397         const ExplodedNode *N = I->second;
 398         std::string stackMsg = ep->getCallStackMessage(N);
 399
 400         // The last message on the path to final bug is the most important
 401         // one. Since we traverse the path backwards, do not add the message
 402         // if one has been previously added.
 403         if  (!CP->hasCallStackMessage())
 404           CP->setCallStackMessage(stackMsg);
 405       }
 406   }
 407 }
 408
 409 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM);
 410
 411 static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD,
 412                                           PathDiagnosticBuilder &PDB,
 413                                           const ExplodedNode *N,
 414                                       ArrayRef<BugReporterVisitor *> visitors) {
 415
 416   SourceManager& SMgr = PDB.getSourceManager();
 417   const LocationContext *LC = PDB.LC;
 418   const ExplodedNode *NextNode = N->pred_empty()
 419                                         ? NULL : *(N->pred_begin());
 420
 421   StackDiagVector CallStack;
 422
 423   while (NextNode) {
 424     N = NextNode;
 425     PDB.LC = N->getLocationContext();
 426     NextNode = GetPredecessorNode(N);
 427
 428     ProgramPoint P = N->getLocation();
 429
 430     if (const CallExit *CE = dyn_cast<CallExit>(&P)) {
 431       PathDiagnosticCallPiece *C =
 432         PathDiagnosticCallPiece::construct(N, *CE, SMgr);
 433       PD.getActivePath().push_front(C);
 434       PD.pushActivePath(&C->path);
 435       CallStack.push_back(StackDiagPair(C, N));
 436       continue;
 437     }
 438
 439     if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) {
 440       PD.popActivePath();
 441       // The current active path should never be empty.  Either we
 442       // just added a bunch of stuff to the top-level path, or
 443       // we have a previous CallExit.  If the front of the active
 444       // path is not a PathDiagnosticCallPiece, it means that the
 445       // path terminated within a function call.  We must then take the
 446       // current contents of the active path and place it within
 447       // a new PathDiagnosticCallPiece.
 448       assert(!PD.getActivePath().empty());
 449       PathDiagnosticCallPiece *C =
 450         dyn_cast<PathDiagnosticCallPiece>(PD.getActivePath().front());
 451       if (!C) {
 452         const Decl *Caller = CE->getLocationContext()->getDecl();
 453         C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller);
 454       }
 455       C->setCallee(*CE, SMgr);
 456       if (!CallStack.empty()) {
 457         assert(CallStack.back().first == C);
 458         CallStack.pop_back();
 459       }
 460       continue;
 461     }
 462
 463     if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
 464       const CFGBlock *Src = BE->getSrc();
 465       const CFGBlock *Dst = BE->getDst();
 466       const Stmt *T = Src->getTerminator();
 467
 468       if (!T)
 469         continue;
 470
 471       PathDiagnosticLocation Start =
 472         PathDiagnosticLocation::createBegin(T, SMgr,
 473                                                 N->getLocationContext());
 474
 475       switch (T->getStmtClass()) {
 476         default:
 477           break;
 478
 479         case Stmt::GotoStmtClass:
 480         case Stmt::IndirectGotoStmtClass: {
 481           const Stmt *S = GetNextStmt(N);
 482
 483           if (!S)
 484             continue;
 485
 486           std::string sbuf;
 487           llvm::raw_string_ostream os(sbuf);
 488           const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S);
 489
 490           os << "Control jumps to line "
 491           << End.asLocation().getExpansionLineNumber();
 492           PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 493                                                                 os.str()));
 494           break;
 495         }
 496
 497         case Stmt::SwitchStmtClass: {
 498           // Figure out what case arm we took.
 499           std::string sbuf;
 500           llvm::raw_string_ostream os(sbuf);
 501
 502           if (const Stmt *S = Dst->getLabel()) {
 503             PathDiagnosticLocation End(S, SMgr, LC);
 504
 505             switch (S->getStmtClass()) {
 506               default:
 507                 os << "No cases match in the switch statement. "
 508                 "Control jumps to line "
 509                 << End.asLocation().getExpansionLineNumber();
 510                 break;
 511               case Stmt::DefaultStmtClass:
 512                 os << "Control jumps to the 'default' case at line "
 513                 << End.asLocation().getExpansionLineNumber();
 514                 break;
 515
 516               case Stmt::CaseStmtClass: {
 517                 os << "Control jumps to 'case ";
 518                 const CaseStmt *Case = cast<CaseStmt>(S);
 519                 const Expr *LHS = Case->getLHS()->IgnoreParenCasts();
 520
 521                 // Determine if it is an enum.
 522                 bool GetRawInt = true;
 523
 524                 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
 525                   // FIXME: Maybe this should be an assertion.  Are there cases
 526                   // were it is not an EnumConstantDecl?
 527                   const EnumConstantDecl *D =
 528                     dyn_cast<EnumConstantDecl>(DR->getDecl());
 529
 530                   if (D) {
 531                     GetRawInt = false;
 532                     os << *D;
 533                   }
 534                 }
 535
 536                 if (GetRawInt)
 537                   os << LHS->EvaluateKnownConstInt(PDB.getASTContext());
 538
 539                 os << ":'  at line "
 540                 << End.asLocation().getExpansionLineNumber();
 541                 break;
 542               }
 543             }
 544             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 545                                                              os.str()));
 546           }
 547           else {
 548             os << "'Default' branch taken. ";
 549             const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N);
 550             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 551                                                              os.str()));
 552           }
 553
 554           break;
 555         }
 556
 557         case Stmt::BreakStmtClass:
 558         case Stmt::ContinueStmtClass: {
 559           std::string sbuf;
 560           llvm::raw_string_ostream os(sbuf);
 561           PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
 562           PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 563                                                            os.str()));
 564           break;
 565         }
 566
 567           // Determine control-flow for ternary '?'.
 568         case Stmt::BinaryConditionalOperatorClass:
 569         case Stmt::ConditionalOperatorClass: {
 570           std::string sbuf;
 571           llvm::raw_string_ostream os(sbuf);
 572           os << "'?' condition is ";
 573
 574           if (*(Src->succ_begin()+1) == Dst)
 575             os << "false";
 576           else
 577             os << "true";
 578
 579           PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 580
 581           if (const Stmt *S = End.asStmt())
 582             End = PDB.getEnclosingStmtLocation(S);
 583
 584           PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 585                                                            os.str()));
 586           break;
 587         }
 588
 589           // Determine control-flow for short-circuited '&&' and '||'.
 590         case Stmt::BinaryOperatorClass: {
 591           if (!PDB.supportsLogicalOpControlFlow())
 592             break;
 593
 594           const BinaryOperator *B = cast<BinaryOperator>(T);
 595           std::string sbuf;
 596           llvm::raw_string_ostream os(sbuf);
 597           os << "Left side of '";
 598
 599           if (B->getOpcode() == BO_LAnd) {
 600             os << "&&" << "' is ";
 601
 602             if (*(Src->succ_begin()+1) == Dst) {
 603               os << "false";
 604               PathDiagnosticLocation End(B->getLHS(), SMgr, LC);
 605               PathDiagnosticLocation Start =
 606                 PathDiagnosticLocation::createOperatorLoc(B, SMgr);
 607               PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 608                                                                os.str()));
 609             }
 610             else {
 611               os << "true";
 612               PathDiagnosticLocation Start(B->getLHS(), SMgr, LC);
 613               PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 614               PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 615                                                                os.str()));
 616             }
 617           }
 618           else {
 619             assert(B->getOpcode() == BO_LOr);
 620             os << "||" << "' is ";
 621
 622             if (*(Src->succ_begin()+1) == Dst) {
 623               os << "false";
 624               PathDiagnosticLocation Start(B->getLHS(), SMgr, LC);
 625               PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 626               PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 627                                                                os.str()));
 628             }
 629             else {
 630               os << "true";
 631               PathDiagnosticLocation End(B->getLHS(), SMgr, LC);
 632               PathDiagnosticLocation Start =
 633                 PathDiagnosticLocation::createOperatorLoc(B, SMgr);
 634               PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 635                                                                os.str()));
 636             }
 637           }
 638
 639           break;
 640         }
 641
 642         case Stmt::DoStmtClass:  {
 643           if (*(Src->succ_begin()) == Dst) {
 644             std::string sbuf;
 645             llvm::raw_string_ostream os(sbuf);
 646
 647             os << "Loop condition is true. ";
 648             PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
 649
 650             if (const Stmt *S = End.asStmt())
 651               End = PDB.getEnclosingStmtLocation(S);
 652
 653             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 654                                                              os.str()));
 655           }
 656           else {
 657             PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 658
 659             if (const Stmt *S = End.asStmt())
 660               End = PDB.getEnclosingStmtLocation(S);
 661
 662             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 663                               "Loop condition is false.  Exiting loop"));
 664           }
 665
 666           break;
 667         }
 668
 669         case Stmt::WhileStmtClass:
 670         case Stmt::ForStmtClass: {
 671           if (*(Src->succ_begin()+1) == Dst) {
 672             std::string sbuf;
 673             llvm::raw_string_ostream os(sbuf);
 674
 675             os << "Loop condition is false. ";
 676             PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
 677             if (const Stmt *S = End.asStmt())
 678               End = PDB.getEnclosingStmtLocation(S);
 679
 680             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 681                                                              os.str()));
 682           }
 683           else {
 684             PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 685             if (const Stmt *S = End.asStmt())
 686               End = PDB.getEnclosingStmtLocation(S);
 687
 688             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 689                             "Loop condition is true.  Entering loop body"));
 690           }
 691
 692           break;
 693         }
 694
 695         case Stmt::IfStmtClass: {
 696           PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 697
 698           if (const Stmt *S = End.asStmt())
 699             End = PDB.getEnclosingStmtLocation(S);
 700
 701           if (*(Src->succ_begin()+1) == Dst)
 702             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 703                                                         "Taking false branch"));
 704           else
 705             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End,
 706                                                          "Taking true branch"));
 707
 708           break;
 709         }
 710       }
 711     }
 712
 713     if (NextNode) {
 714       // Add diagnostic pieces from custom visitors.
 715       BugReport *R = PDB.getBugReport();
 716       for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
 717                                                     E = visitors.end();
 718            I != E; ++I) {
 719         if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) {
 720           PD.getActivePath().push_front(p);
 721           updateStackPiecesWithMessage(p, CallStack);
 722         }
 723       }
 724     }
 725   }
 726
 727   // After constructing the full PathDiagnostic, do a pass over it to compact
 728   // PathDiagnosticPieces that occur within a macro.
 729   CompactPathDiagnostic(PD.getMutablePieces(), PDB.getSourceManager());
 730 }
 731
 732 //===----------------------------------------------------------------------===//
 733 // "Extensive" PathDiagnostic generation.
 734 //===----------------------------------------------------------------------===//
 735
 736 static bool IsControlFlowExpr(const Stmt *S) {
 737   const Expr *E = dyn_cast<Expr>(S);
 738
 739   if (!E)
 740     return false;
 741
 742   E = E->IgnoreParenCasts();
 743
 744   if (isa<AbstractConditionalOperator>(E))
 745     return true;
 746
 747   if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E))
 748     if (B->isLogicalOp())
 749       return true;
 750
 751   return false;
 752 }
 753
 754 namespace {
 755 class ContextLocation : public PathDiagnosticLocation {
 756   bool IsDead;
 757 public:
 758   ContextLocation(const PathDiagnosticLocation &L, bool isdead = false)
 759     : PathDiagnosticLocation(L), IsDead(isdead) {}
 760
 761   void markDead() { IsDead = true; }
 762   bool isDead() const { return IsDead; }
 763 };
 764
 765 class EdgeBuilder {
 766   std::vector<ContextLocation> CLocs;
 767   typedef std::vector<ContextLocation>::iterator iterator;
 768   PathDiagnostic &PD;
 769   PathDiagnosticBuilder &PDB;
 770   PathDiagnosticLocation PrevLoc;
 771
 772   bool IsConsumedExpr(const PathDiagnosticLocation &L);
 773
 774   bool containsLocation(const PathDiagnosticLocation &Container,
 775                         const PathDiagnosticLocation &Containee);
 776
 777   PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L);
 778
 779   PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L,
 780                                          bool firstCharOnly = false) {
 781     if (const Stmt *S = L.asStmt()) {
 782       const Stmt *Original = S;
 783       while (1) {
 784         // Adjust the location for some expressions that are best referenced
 785         // by one of their subexpressions.
 786         switch (S->getStmtClass()) {
 787           default:
 788             break;
 789           case Stmt::ParenExprClass:
 790           case Stmt::GenericSelectionExprClass:
 791             S = cast<Expr>(S)->IgnoreParens();
 792             firstCharOnly = true;
 793             continue;
 794           case Stmt::BinaryConditionalOperatorClass:
 795           case Stmt::ConditionalOperatorClass:
 796             S = cast<AbstractConditionalOperator>(S)->getCond();
 797             firstCharOnly = true;
 798             continue;
 799           case Stmt::ChooseExprClass:
 800             S = cast<ChooseExpr>(S)->getCond();
 801             firstCharOnly = true;
 802             continue;
 803           case Stmt::BinaryOperatorClass:
 804             S = cast<BinaryOperator>(S)->getLHS();
 805             firstCharOnly = true;
 806             continue;
 807         }
 808
 809         break;
 810       }
 811
 812       if (S != Original)
 813         L = PathDiagnosticLocation(S, L.getManager(), PDB.LC);
 814     }
 815
 816     if (firstCharOnly)
 817       L  = PathDiagnosticLocation::createSingleLocation(L);
 818
 819     return L;
 820   }
 821
 822   void popLocation() {
 823     if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) {
 824       // For contexts, we only one the first character as the range.
 825       rawAddEdge(cleanUpLocation(CLocs.back(), true));
 826     }
 827     CLocs.pop_back();
 828   }
 829
 830 public:
 831   EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb)
 832     : PD(pd), PDB(pdb) {
 833
 834       // If the PathDiagnostic already has pieces, add the enclosing statement
 835       // of the first piece as a context as well.
 836       if (!PD.path.empty()) {
 837         PrevLoc = (*PD.path.begin())->getLocation();
 838
 839         if (const Stmt *S = PrevLoc.asStmt())
 840           addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
 841       }
 842   }
 843
 844   ~EdgeBuilder() {
 845     while (!CLocs.empty()) popLocation();
 846
 847     // Finally, add an initial edge from the start location of the first
 848     // statement (if it doesn't already exist).
 849     PathDiagnosticLocation L = PathDiagnosticLocation::createDeclBegin(
 850                                                        PDB.LC,
 851                                                        PDB.getSourceManager());
 852     if (L.isValid())
 853       rawAddEdge(L);
 854   }
 855
 856   void flushLocations() {
 857     while (!CLocs.empty())
 858       popLocation();
 859     PrevLoc = PathDiagnosticLocation();
 860   }
 861
 862   void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false);
 863
 864   void rawAddEdge(PathDiagnosticLocation NewLoc);
 865
 866   void addContext(const Stmt *S);
 867   void addExtendedContext(const Stmt *S);
 868 };
 869 } // end anonymous namespace
 870
 871
 872 PathDiagnosticLocation
 873 EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) {
 874   if (const Stmt *S = L.asStmt()) {
 875     if (IsControlFlowExpr(S))
 876       return L;
 877
 878     return PDB.getEnclosingStmtLocation(S);
 879   }
 880
 881   return L;
 882 }
 883
 884 bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container,
 885                                    const PathDiagnosticLocation &Containee) {
 886
 887   if (Container == Containee)
 888     return true;
 889
 890   if (Container.asDecl())
 891     return true;
 892
 893   if (const Stmt *S = Containee.asStmt())
 894     if (const Stmt *ContainerS = Container.asStmt()) {
 895       while (S) {
 896         if (S == ContainerS)
 897           return true;
 898         S = PDB.getParent(S);
 899       }
 900       return false;
 901     }
 902
 903   // Less accurate: compare using source ranges.
 904   SourceRange ContainerR = Container.asRange();
 905   SourceRange ContaineeR = Containee.asRange();
 906
 907   SourceManager &SM = PDB.getSourceManager();
 908   SourceLocation ContainerRBeg = SM.getExpansionLoc(ContainerR.getBegin());
 909   SourceLocation ContainerREnd = SM.getExpansionLoc(ContainerR.getEnd());
 910   SourceLocation ContaineeRBeg = SM.getExpansionLoc(ContaineeR.getBegin());
 911   SourceLocation ContaineeREnd = SM.getExpansionLoc(ContaineeR.getEnd());
 912
 913   unsigned ContainerBegLine = SM.getExpansionLineNumber(ContainerRBeg);
 914   unsigned ContainerEndLine = SM.getExpansionLineNumber(ContainerREnd);
 915   unsigned ContaineeBegLine = SM.getExpansionLineNumber(ContaineeRBeg);
 916   unsigned ContaineeEndLine = SM.getExpansionLineNumber(ContaineeREnd);
 917
 918   assert(ContainerBegLine <= ContainerEndLine);
 919   assert(ContaineeBegLine <= ContaineeEndLine);
 920
 921   return (ContainerBegLine <= ContaineeBegLine &&
 922           ContainerEndLine >= ContaineeEndLine &&
 923           (ContainerBegLine != ContaineeBegLine ||
 924            SM.getExpansionColumnNumber(ContainerRBeg) <=
 925            SM.getExpansionColumnNumber(ContaineeRBeg)) &&
 926           (ContainerEndLine != ContaineeEndLine ||
 927            SM.getExpansionColumnNumber(ContainerREnd) >=
 928            SM.getExpansionColumnNumber(ContaineeREnd)));
 929 }
 930
 931 void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) {
 932   if (!PrevLoc.isValid()) {
 933     PrevLoc = NewLoc;
 934     return;
 935   }
 936
 937   const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc);
 938   const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc);
 939
 940   if (NewLocClean.asLocation() == PrevLocClean.asLocation())
 941     return;
 942
 943   // FIXME: Ignore intra-macro edges for now.
 944   if (NewLocClean.asLocation().getExpansionLoc() ==
 945       PrevLocClean.asLocation().getExpansionLoc())
 946     return;
 947
 948   PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean));
 949   PrevLoc = NewLoc;
 950 }
 951
 952 void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd) {
 953
 954   if (!alwaysAdd && NewLoc.asLocation().isMacroID())
 955     return;
 956
 957   const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc);
 958
 959   while (!CLocs.empty()) {
 960     ContextLocation &TopContextLoc = CLocs.back();
 961
 962     // Is the top location context the same as the one for the new location?
 963     if (TopContextLoc == CLoc) {
 964       if (alwaysAdd) {
 965         if (IsConsumedExpr(TopContextLoc) &&
 966             !IsControlFlowExpr(TopContextLoc.asStmt()))
 967             TopContextLoc.markDead();
 968
 969         rawAddEdge(NewLoc);
 970       }
 971
 972       return;
 973     }
 974
 975     if (containsLocation(TopContextLoc, CLoc)) {
 976       if (alwaysAdd) {
 977         rawAddEdge(NewLoc);
 978
 979         if (IsConsumedExpr(CLoc) && !IsControlFlowExpr(CLoc.asStmt())) {
 980           CLocs.push_back(ContextLocation(CLoc, true));
 981           return;
 982         }
 983       }
 984
 985       CLocs.push_back(CLoc);
 986       return;
 987     }
 988
 989     // Context does not contain the location.  Flush it.
 990     popLocation();
 991   }
 992
 993   // If we reach here, there is no enclosing context.  Just add the edge.
 994   rawAddEdge(NewLoc);
 995 }
 996
 997 bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) {
 998   if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt()))
 999     return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X);
1000
1001   return false;
1002 }
1003
1004 void EdgeBuilder::addExtendedContext(const Stmt *S) {
1005   if (!S)
1006     return;
1007
1008   const Stmt *Parent = PDB.getParent(S);
1009   while (Parent) {
1010     if (isa<CompoundStmt>(Parent))
1011       Parent = PDB.getParent(Parent);
1012     else
1013       break;
1014   }
1015
1016   if (Parent) {
1017     switch (Parent->getStmtClass()) {
1018       case Stmt::DoStmtClass:
1019       case Stmt::ObjCAtSynchronizedStmtClass:
1020         addContext(Parent);
1021       default:
1022         break;
1023     }
1024   }
1025
1026   addContext(S);
1027 }
1028
1029 void EdgeBuilder::addContext(const Stmt *S) {
1030   if (!S)
1031     return;
1032
1033   PathDiagnosticLocation L(S, PDB.getSourceManager(), PDB.LC);
1034
1035   while (!CLocs.empty()) {
1036     const PathDiagnosticLocation &TopContextLoc = CLocs.back();
1037
1038     // Is the top location context the same as the one for the new location?
1039     if (TopContextLoc == L)
1040       return;
1041
1042     if (containsLocation(TopContextLoc, L)) {
1043       CLocs.push_back(L);
1044       return;
1045     }
1046
1047     // Context does not contain the location.  Flush it.
1048     popLocation();
1049   }
1050
1051   CLocs.push_back(L);
1052 }
1053
1054 static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD,
1055                                             PathDiagnosticBuilder &PDB,
1056                                             const ExplodedNode *N,
1057                                       ArrayRef<BugReporterVisitor *> visitors) {
1058   EdgeBuilder EB(PD, PDB);
1059   const SourceManager& SM = PDB.getSourceManager();
1060   StackDiagVector CallStack;
1061
1062   const ExplodedNode *NextNode = N->pred_empty() ? NULL : *(N->pred_begin());
1063   while (NextNode) {
1064     N = NextNode;
1065     NextNode = GetPredecessorNode(N);
1066     ProgramPoint P = N->getLocation();
1067
1068     do {
1069       if (const CallExit *CE = dyn_cast<CallExit>(&P)) {
1070         const StackFrameContext *LCtx =
1071         CE->getLocationContext()->getCurrentStackFrame();
1072         PathDiagnosticLocation Loc(LCtx->getCallSite(),
1073                                    PDB.getSourceManager(),
1074                                    LCtx);
1075         EB.addEdge(Loc, true);
1076         EB.flushLocations();
1077         PathDiagnosticCallPiece *C =
1078           PathDiagnosticCallPiece::construct(N, *CE, SM);
1079         PD.getActivePath().push_front(C);
1080         PD.pushActivePath(&C->path);
1081         CallStack.push_back(StackDiagPair(C, N));
1082         break;
1083       }
1084
1085       // Pop the call hierarchy if we are done walking the contents
1086       // of a function call.
1087       if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) {
1088         // Add an edge to the start of the function.
1089         const Decl *D = CE->getCalleeContext()->getDecl();
1090         PathDiagnosticLocation pos =
1091           PathDiagnosticLocation::createBegin(D, SM);
1092         EB.addEdge(pos);
1093
1094         // Flush all locations, and pop the active path.
1095         EB.flushLocations();
1096         PD.popActivePath();
1097         assert(!PD.getActivePath().empty());
1098         PDB.LC = N->getLocationContext();
1099
1100         // The current active path should never be empty.  Either we
1101         // just added a bunch of stuff to the top-level path, or
1102         // we have a previous CallExit.  If the front of the active
1103         // path is not a PathDiagnosticCallPiece, it means that the
1104         // path terminated within a function call.  We must then take the
1105         // current contents of the active path and place it within
1106         // a new PathDiagnosticCallPiece.
1107         PathDiagnosticCallPiece *C =
1108           dyn_cast<PathDiagnosticCallPiece>(PD.getActivePath().front());
1109         if (!C) {
1110           const Decl * Caller = CE->getLocationContext()->getDecl();
1111           C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller);
1112         }
1113         C->setCallee(*CE, SM);
1114         EB.addContext(CE->getCallExpr());
1115
1116         if (!CallStack.empty()) {
1117           assert(CallStack.back().first == C);
1118           CallStack.pop_back();
1119         }
1120         break;
1121       }
1122
1123       // Note that is important that we update the LocationContext
1124       // after looking at CallExits.  CallExit basically adds an
1125       // edge in the *caller*, so we don't want to update the LocationContext
1126       // too soon.
1127       PDB.LC = N->getLocationContext();
1128
1129       // Block edges.
1130       if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
1131         const CFGBlock &Blk = *BE->getSrc();
1132         const Stmt *Term = Blk.getTerminator();
1133
1134         // Are we jumping to the head of a loop?  Add a special diagnostic.
1135         if (const Stmt *Loop = BE->getDst()->getLoopTarget()) {
1136           PathDiagnosticLocation L(Loop, SM, PDB.LC);
1137           const CompoundStmt *CS = NULL;
1138
1139           if (!Term) {
1140             if (const ForStmt *FS = dyn_cast<ForStmt>(Loop))
1141               CS = dyn_cast<CompoundStmt>(FS->getBody());
1142             else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop))
1143               CS = dyn_cast<CompoundStmt>(WS->getBody());
1144           }
1145
1146           PathDiagnosticEventPiece *p =
1147             new PathDiagnosticEventPiece(L,
1148                                         "Looping back to the head of the loop");
1149           p->setPrunable(true);
1150
1151           EB.addEdge(p->getLocation(), true);
1152           PD.getActivePath().push_front(p);
1153
1154           if (CS) {
1155             PathDiagnosticLocation BL =
1156               PathDiagnosticLocation::createEndBrace(CS, SM);
1157             EB.addEdge(BL);
1158           }
1159         }
1160
1161         if (Term)
1162           EB.addContext(Term);
1163
1164         break;
1165       }
1166
1167       if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) {
1168         if (const CFGStmt *S = BE->getFirstElement().getAs<CFGStmt>()) {
1169           const Stmt *stmt = S->getStmt();
1170           if (IsControlFlowExpr(stmt)) {
1171             // Add the proper context for '&&', '||', and '?'.
1172             EB.addContext(stmt);
1173           }
1174           else
1175             EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt());
1176         }
1177
1178         break;
1179       }
1180
1181
1182     } while (0);
1183
1184     if (!NextNode)
1185       continue;
1186
1187     // Add pieces from custom visitors.
1188     BugReport *R = PDB.getBugReport();
1189     for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
1190                                                   E = visitors.end();
1191          I != E; ++I) {
1192       if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) {
1193         const PathDiagnosticLocation &Loc = p->getLocation();
1194         EB.addEdge(Loc, true);
1195         PD.getActivePath().push_front(p);
1196         updateStackPiecesWithMessage(p, CallStack);
1197
1198         if (const Stmt *S = Loc.asStmt())
1199           EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1200       }
1201     }
1202   }
1203 }
1204
1205 //===----------------------------------------------------------------------===//
1206 // Methods for BugType and subclasses.
1207 //===----------------------------------------------------------------------===//
1208 BugType::~BugType() { }
1209
1210 void BugType::FlushReports(BugReporter &BR) {}
1211
1212 void BuiltinBug::anchor() {}
1213
1214 //===----------------------------------------------------------------------===//
1215 // Methods for BugReport and subclasses.
1216 //===----------------------------------------------------------------------===//
1217
1218 void BugReport::NodeResolver::anchor() {}
1219
1220 void BugReport::addVisitor(BugReporterVisitor* visitor) {
1221   if (!visitor)
1222     return;
1223
1224   llvm::FoldingSetNodeID ID;
1225   visitor->Profile(ID);
1226   void *InsertPos;
1227
1228   if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) {
1229     delete visitor;
1230     return;
1231   }
1232
1233   CallbacksSet.InsertNode(visitor, InsertPos);
1234   Callbacks.push_back(visitor);
1235   ++ConfigurationChangeToken;
1236 }
1237
1238 BugReport::~BugReport() {
1239   for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I) {
1240     delete *I;
1241   }
1242 }
1243
1244 const Decl *BugReport::getDeclWithIssue() const {
1245   if (DeclWithIssue)
1246     return DeclWithIssue;
1247
1248   const ExplodedNode *N = getErrorNode();
1249   if (!N)
1250     return 0;
1251
1252   const LocationContext *LC = N->getLocationContext();
1253   return LC->getCurrentStackFrame()->getDecl();
1254 }
1255
1256 void BugReport::Profile(llvm::FoldingSetNodeID& hash) const {
1257   hash.AddPointer(&BT);
1258   hash.AddString(Description);
1259   if (UniqueingLocation.isValid()) {
1260     UniqueingLocation.Profile(hash);
1261   } else if (Location.isValid()) {
1262     Location.Profile(hash);
1263   } else {
1264     assert(ErrorNode);
1265     hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode));
1266   }
1267
1268   for (SmallVectorImpl<SourceRange>::const_iterator I =
1269       Ranges.begin(), E = Ranges.end(); I != E; ++I) {
1270     const SourceRange range = *I;
1271     if (!range.isValid())
1272       continue;
1273     hash.AddInteger(range.getBegin().getRawEncoding());
1274     hash.AddInteger(range.getEnd().getRawEncoding());
1275   }
1276 }
1277
1278 void BugReport::markInteresting(SymbolRef sym) {
1279   if (!sym)
1280     return;
1281
1282   // If the symbol wasn't already in our set, note a configuration change.
1283   if (interestingSymbols.insert(sym).second)
1284     ++ConfigurationChangeToken;
1285
1286   if (const SymbolMetadata *meta = dyn_cast<SymbolMetadata>(sym))
1287     interestingRegions.insert(meta->getRegion());
1288 }
1289
1290 void BugReport::markInteresting(const MemRegion *R) {
1291   if (!R)
1292     return;
1293
1294   // If the base region wasn't already in our set, note a configuration change.
1295   R = R->getBaseRegion();
1296   if (interestingRegions.insert(R).second)
1297     ++ConfigurationChangeToken;
1298
1299   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
1300     interestingSymbols.insert(SR->getSymbol());
1301 }
1302
1303 void BugReport::markInteresting(SVal V) {
1304   markInteresting(V.getAsRegion());
1305   markInteresting(V.getAsSymbol());
1306 }
1307
1308 bool BugReport::isInteresting(SVal V) const {
1309   return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol());
1310 }
1311
1312 bool BugReport::isInteresting(SymbolRef sym) const {
1313   if (!sym)
1314     return false;
1315   // We don't currently consider metadata symbols to be interesting
1316   // even if we know their region is interesting. Is that correct behavior?
1317   return interestingSymbols.count(sym);
1318 }
1319
1320 bool BugReport::isInteresting(const MemRegion *R) const {
1321   if (!R)
1322     return false;
1323   R = R->getBaseRegion();
1324   bool b = interestingRegions.count(R);
1325   if (b)
1326     return true;
1327   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
1328     return interestingSymbols.count(SR->getSymbol());
1329   return false;
1330 }
1331
1332
1333 const Stmt *BugReport::getStmt() const {
1334   if (!ErrorNode)
1335     return 0;
1336
1337   ProgramPoint ProgP = ErrorNode->getLocation();
1338   const Stmt *S = NULL;
1339
1340   if (BlockEntrance *BE = dyn_cast<BlockEntrance>(&ProgP)) {
1341     CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
1342     if (BE->getBlock() == &Exit)
1343       S = GetPreviousStmt(ErrorNode);
1344   }
1345   if (!S)
1346     S = GetStmt(ProgP);
1347
1348   return S;
1349 }
1350
1351 std::pair<BugReport::ranges_iterator, BugReport::ranges_iterator>
1352 BugReport::getRanges() {
1353     // If no custom ranges, add the range of the statement corresponding to
1354     // the error node.
1355     if (Ranges.empty()) {
1356       if (const Expr *E = dyn_cast_or_null<Expr>(getStmt()))
1357         addRange(E->getSourceRange());
1358       else
1359         return std::make_pair(ranges_iterator(), ranges_iterator());
1360     }
1361
1362     // User-specified absence of range info.
1363     if (Ranges.size() == 1 && !Ranges.begin()->isValid())
1364       return std::make_pair(ranges_iterator(), ranges_iterator());
1365
1366     return std::make_pair(Ranges.begin(), Ranges.end());
1367 }
1368
1369 PathDiagnosticLocation BugReport::getLocation(const SourceManager &SM) const {
1370   if (ErrorNode) {
1371     assert(!Location.isValid() &&
1372      "Either Location or ErrorNode should be specified but not both.");
1373
1374     if (const Stmt *S = GetCurrentOrPreviousStmt(ErrorNode)) {
1375       const LocationContext *LC = ErrorNode->getLocationContext();
1376
1377       // For member expressions, return the location of the '.' or '->'.
1378       if (const MemberExpr *ME = dyn_cast<MemberExpr>(S))
1379         return PathDiagnosticLocation::createMemberLoc(ME, SM);
1380       // For binary operators, return the location of the operator.
1381       if (const BinaryOperator *B = dyn_cast<BinaryOperator>(S))
1382         return PathDiagnosticLocation::createOperatorLoc(B, SM);
1383
1384       return PathDiagnosticLocation::createBegin(S, SM, LC);
1385     }
1386   } else {
1387     assert(Location.isValid());
1388     return Location;
1389   }
1390
1391   return PathDiagnosticLocation();
1392 }
1393
1394 //===----------------------------------------------------------------------===//
1395 // Methods for BugReporter and subclasses.
1396 //===----------------------------------------------------------------------===//
1397
1398 BugReportEquivClass::~BugReportEquivClass() { }
1399 GRBugReporter::~GRBugReporter() { }
1400 BugReporterData::~BugReporterData() {}
1401
1402 ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
1403
1404 ProgramStateManager&
1405 GRBugReporter::getStateManager() { return Eng.getStateManager(); }
1406
1407 BugReporter::~BugReporter() {
1408   FlushReports();
1409
1410   // Free the bug reports we are tracking.
1411   typedef std::vector<BugReportEquivClass *> ContTy;
1412   for (ContTy::iterator I = EQClassesVector.begin(), E = EQClassesVector.end();
1413        I != E; ++I) {
1414     delete *I;
1415   }
1416 }
1417
1418 void BugReporter::FlushReports() {
1419   if (BugTypes.isEmpty())
1420     return;
1421
1422   // First flush the warnings for each BugType.  This may end up creating new
1423   // warnings and new BugTypes.
1424   // FIXME: Only NSErrorChecker needs BugType's FlushReports.
1425   // Turn NSErrorChecker into a proper checker and remove this.
1426   SmallVector<const BugType*, 16> bugTypes;
1427   for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I)
1428     bugTypes.push_back(*I);
1429   for (SmallVector<const BugType*, 16>::iterator
1430          I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I)
1431     const_cast<BugType*>(*I)->FlushReports(*this);
1432
1433   typedef llvm::FoldingSet<BugReportEquivClass> SetTy;
1434   for (SetTy::iterator EI=EQClasses.begin(), EE=EQClasses.end(); EI!=EE;++EI){
1435     BugReportEquivClass& EQ = *EI;
1436     FlushReport(EQ);
1437   }
1438
1439   // BugReporter owns and deletes only BugTypes created implicitly through
1440   // EmitBasicReport.
1441   // FIXME: There are leaks from checkers that assume that the BugTypes they
1442   // create will be destroyed by the BugReporter.
1443   for (llvm::StringMap<BugType*>::iterator
1444          I = StrBugTypes.begin(), E = StrBugTypes.end(); I != E; ++I)
1445     delete I->second;
1446
1447   // Remove all references to the BugType objects.
1448   BugTypes = F.getEmptySet();
1449 }
1450
1451 //===----------------------------------------------------------------------===//
1452 // PathDiagnostics generation.
1453 //===----------------------------------------------------------------------===//
1454
1455 static std::pair<std::pair<ExplodedGraph*, NodeBackMap*>,
1456                  std::pair<ExplodedNode*, unsigned> >
1457 MakeReportGraph(const ExplodedGraph* G,
1458                 SmallVectorImpl<const ExplodedNode*> &nodes) {
1459
1460   // Create the trimmed graph.  It will contain the shortest paths from the
1461   // error nodes to the root.  In the new graph we should only have one
1462   // error node unless there are two or more error nodes with the same minimum
1463   // path length.
1464   ExplodedGraph* GTrim;
1465   InterExplodedGraphMap* NMap;
1466
1467   llvm::DenseMap<const void*, const void*> InverseMap;
1468   llvm::tie(GTrim, NMap) = G->Trim(nodes.data(), nodes.data() + nodes.size(),
1469                                    &InverseMap);
1470
1471   // Create owning pointers for GTrim and NMap just to ensure that they are
1472   // released when this function exists.
1473   OwningPtr<ExplodedGraph> AutoReleaseGTrim(GTrim);
1474   OwningPtr<InterExplodedGraphMap> AutoReleaseNMap(NMap);
1475
1476   // Find the (first) error node in the trimmed graph.  We just need to consult
1477   // the node map (NMap) which maps from nodes in the original graph to nodes
1478   // in the new graph.
1479
1480   std::queue<const ExplodedNode*> WS;
1481   typedef llvm::DenseMap<const ExplodedNode*, unsigned> IndexMapTy;
1482   IndexMapTy IndexMap;
1483
1484   for (unsigned nodeIndex = 0 ; nodeIndex < nodes.size(); ++nodeIndex) {
1485     const ExplodedNode *originalNode = nodes[nodeIndex];
1486     if (const ExplodedNode *N = NMap->getMappedNode(originalNode)) {
1487       WS.push(N);
1488       IndexMap[originalNode] = nodeIndex;
1489     }
1490   }
1491
1492   assert(!WS.empty() && "No error node found in the trimmed graph.");
1493
1494   // Create a new (third!) graph with a single path.  This is the graph
1495   // that will be returned to the caller.
1496   ExplodedGraph *GNew = new ExplodedGraph();
1497
1498   // Sometimes the trimmed graph can contain a cycle.  Perform a reverse BFS
1499   // to the root node, and then construct a new graph that contains only
1500   // a single path.
1501   llvm::DenseMap<const void*,unsigned> Visited;
1502
1503   unsigned cnt = 0;
1504   const ExplodedNode *Root = 0;
1505
1506   while (!WS.empty()) {
1507     const ExplodedNode *Node = WS.front();
1508     WS.pop();
1509
1510     if (Visited.find(Node) != Visited.end())
1511       continue;
1512
1513     Visited[Node] = cnt++;
1514
1515     if (Node->pred_empty()) {
1516       Root = Node;
1517       break;
1518     }
1519
1520     for (ExplodedNode::const_pred_iterator I=Node->pred_begin(),
1521          E=Node->pred_end(); I!=E; ++I)
1522       WS.push(*I);
1523   }
1524
1525   assert(Root);
1526
1527   // Now walk from the root down the BFS path, always taking the successor
1528   // with the lowest number.
1529   ExplodedNode *Last = 0, *First = 0;
1530   NodeBackMap *BM = new NodeBackMap();
1531   unsigned NodeIndex = 0;
1532
1533   for ( const ExplodedNode *N = Root ;;) {
1534     // Lookup the number associated with the current node.
1535     llvm::DenseMap<const void*,unsigned>::iterator I = Visited.find(N);
1536     assert(I != Visited.end());
1537
1538     // Create the equivalent node in the new graph with the same state
1539     // and location.
1540     ExplodedNode *NewN = GNew->getNode(N->getLocation(), N->getState());
1541
1542     // Store the mapping to the original node.
1543     llvm::DenseMap<const void*, const void*>::iterator IMitr=InverseMap.find(N);
1544     assert(IMitr != InverseMap.end() && "No mapping to original node.");
1545     (*BM)[NewN] = (const ExplodedNode*) IMitr->second;
1546
1547     // Link up the new node with the previous node.
1548     if (Last)
1549       NewN->addPredecessor(Last, *GNew);
1550
1551     Last = NewN;
1552
1553     // Are we at the final node?
1554     IndexMapTy::iterator IMI =
1555       IndexMap.find((const ExplodedNode*)(IMitr->second));
1556     if (IMI != IndexMap.end()) {
1557       First = NewN;
1558       NodeIndex = IMI->second;
1559       break;
1560     }
1561
1562     // Find the next successor node.  We choose the node that is marked
1563     // with the lowest DFS number.
1564     ExplodedNode::const_succ_iterator SI = N->succ_begin();
1565     ExplodedNode::const_succ_iterator SE = N->succ_end();
1566     N = 0;
1567
1568     for (unsigned MinVal = 0; SI != SE; ++SI) {
1569
1570       I = Visited.find(*SI);
1571
1572       if (I == Visited.end())
1573         continue;
1574
1575       if (!N || I->second < MinVal) {
1576         N = *SI;
1577         MinVal = I->second;
1578       }
1579     }
1580
1581     assert(N);
1582   }
1583
1584   assert(First);
1585
1586   return std::make_pair(std::make_pair(GNew, BM),
1587                         std::make_pair(First, NodeIndex));
1588 }
1589
1590 /// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
1591 ///  and collapses PathDiagosticPieces that are expanded by macros.
1592 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) {
1593   typedef std::vector<std::pair<IntrusiveRefCntPtr<PathDiagnosticMacroPiece>,
1594                                 SourceLocation> > MacroStackTy;
1595
1596   typedef std::vector<IntrusiveRefCntPtr<PathDiagnosticPiece> >
1597           PiecesTy;
1598
1599   MacroStackTy MacroStack;
1600   PiecesTy Pieces;
1601
1602   for (PathPieces::const_iterator I = path.begin(), E = path.end();
1603        I!=E; ++I) {
1604
1605     PathDiagnosticPiece *piece = I->getPtr();
1606
1607     // Recursively compact calls.
1608     if (PathDiagnosticCallPiece *call=dyn_cast<PathDiagnosticCallPiece>(piece)){
1609       CompactPathDiagnostic(call->path, SM);
1610     }
1611
1612     // Get the location of the PathDiagnosticPiece.
1613     const FullSourceLoc Loc = piece->getLocation().asLocation();
1614
1615     // Determine the instantiation location, which is the location we group
1616     // related PathDiagnosticPieces.
1617     SourceLocation InstantiationLoc = Loc.isMacroID() ?
1618                                       SM.getExpansionLoc(Loc) :
1619                                       SourceLocation();
1620
1621     if (Loc.isFileID()) {
1622       MacroStack.clear();
1623       Pieces.push_back(piece);
1624       continue;
1625     }
1626
1627     assert(Loc.isMacroID());
1628
1629     // Is the PathDiagnosticPiece within the same macro group?
1630     if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
1631       MacroStack.back().first->subPieces.push_back(piece);
1632       continue;
1633     }
1634
1635     // We aren't in the same group.  Are we descending into a new macro
1636     // or are part of an old one?
1637     IntrusiveRefCntPtr<PathDiagnosticMacroPiece> MacroGroup;
1638
1639     SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
1640                                           SM.getExpansionLoc(Loc) :
1641                                           SourceLocation();
1642
1643     // Walk the entire macro stack.
1644     while (!MacroStack.empty()) {
1645       if (InstantiationLoc == MacroStack.back().second) {
1646         MacroGroup = MacroStack.back().first;
1647         break;
1648       }
1649
1650       if (ParentInstantiationLoc == MacroStack.back().second) {
1651         MacroGroup = MacroStack.back().first;
1652         break;
1653       }
1654
1655       MacroStack.pop_back();
1656     }
1657
1658     if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
1659       // Create a new macro group and add it to the stack.
1660       PathDiagnosticMacroPiece *NewGroup =
1661         new PathDiagnosticMacroPiece(
1662           PathDiagnosticLocation::createSingleLocation(piece->getLocation()));
1663
1664       if (MacroGroup)
1665         MacroGroup->subPieces.push_back(NewGroup);
1666       else {
1667         assert(InstantiationLoc.isFileID());
1668         Pieces.push_back(NewGroup);
1669       }
1670
1671       MacroGroup = NewGroup;
1672       MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
1673     }
1674
1675     // Finally, add the PathDiagnosticPiece to the group.
1676     MacroGroup->subPieces.push_back(piece);
1677   }
1678
1679   // Now take the pieces and construct a new PathDiagnostic.
1680   path.clear();
1681
1682   for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I)
1683     path.push_back(*I);
1684 }
1685
1686 void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD,
1687                         SmallVectorImpl<BugReport *> &bugReports) {
1688
1689   assert(!bugReports.empty());
1690   SmallVector<const ExplodedNode *, 10> errorNodes;
1691   for (SmallVectorImpl<BugReport*>::iterator I = bugReports.begin(),
1692     E = bugReports.end(); I != E; ++I) {
1693       errorNodes.push_back((*I)->getErrorNode());
1694   }
1695
1696   // Construct a new graph that contains only a single path from the error
1697   // node to a root.
1698   const std::pair<std::pair<ExplodedGraph*, NodeBackMap*>,
1699   std::pair<ExplodedNode*, unsigned> >&
1700     GPair = MakeReportGraph(&getGraph(), errorNodes);
1701
1702   // Find the BugReport with the original location.
1703   assert(GPair.second.second < bugReports.size());
1704   BugReport *R = bugReports[GPair.second.second];
1705   assert(R && "No original report found for sliced graph.");
1706
1707   OwningPtr<ExplodedGraph> ReportGraph(GPair.first.first);
1708   OwningPtr<NodeBackMap> BackMap(GPair.first.second);
1709   const ExplodedNode *N = GPair.second.first;
1710
1711   // Start building the path diagnostic...
1712   PathDiagnosticBuilder PDB(*this, R, BackMap.get(),
1713                             getPathDiagnosticConsumer());
1714
1715   // Register additional node visitors.
1716   R->addVisitor(new NilReceiverBRVisitor());
1717   R->addVisitor(new ConditionBRVisitor());
1718
1719   BugReport::VisitorList visitors;
1720   unsigned originalReportConfigToken, finalReportConfigToken;
1721
1722   // While generating diagnostics, it's possible the visitors will decide
1723   // new symbols and regions are interesting, or add other visitors based on
1724   // the information they find. If they do, we need to regenerate the path
1725   // based on our new report configuration.
1726   do {
1727     // Get a clean copy of all the visitors.
1728     for (BugReport::visitor_iterator I = R->visitor_begin(),
1729                                      E = R->visitor_end(); I != E; ++I)
1730        visitors.push_back((*I)->clone());
1731
1732     // Clear out the active path from any previous work.
1733     PD.getActivePath().clear();
1734     originalReportConfigToken = R->getConfigurationChangeToken();
1735
1736     // Generate the very last diagnostic piece - the piece is visible before
1737     // the trace is expanded.
1738     PathDiagnosticPiece *LastPiece = 0;
1739     for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end();
1740          I != E; ++I) {
1741       if (PathDiagnosticPiece *Piece = (*I)->getEndPath(PDB, N, *R)) {
1742         assert (!LastPiece &&
1743                 "There can only be one final piece in a diagnostic.");
1744         LastPiece = Piece;
1745       }
1746     }
1747     if (!LastPiece)
1748       LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R);
1749     if (LastPiece)
1750       PD.getActivePath().push_back(LastPiece);
1751     else
1752       return;
1753
1754     switch (PDB.getGenerationScheme()) {
1755     case PathDiagnosticConsumer::Extensive:
1756       GenerateExtensivePathDiagnostic(PD, PDB, N, visitors);
1757       break;
1758     case PathDiagnosticConsumer::Minimal:
1759       GenerateMinimalPathDiagnostic(PD, PDB, N, visitors);
1760       break;
1761     }
1762
1763     // Clean up the visitors we used.
1764     llvm::DeleteContainerPointers(visitors);
1765
1766     // Did anything change while generating this path?
1767     finalReportConfigToken = R->getConfigurationChangeToken();
1768   } while(finalReportConfigToken != originalReportConfigToken);
1769
1770   // Finally, prune the diagnostic path of uninteresting stuff.
1771   bool hasSomethingInteresting = RemoveUneededCalls(PD.getMutablePieces());
1772   assert(hasSomethingInteresting);
1773   (void) hasSomethingInteresting;
1774 }
1775
1776 void BugReporter::Register(BugType *BT) {
1777   BugTypes = F.add(BugTypes, BT);
1778 }
1779
1780 void BugReporter::EmitReport(BugReport* R) {
1781   // Compute the bug report's hash to determine its equivalence class.
1782   llvm::FoldingSetNodeID ID;
1783   R->Profile(ID);
1784
1785   // Lookup the equivance class.  If there isn't one, create it.
1786   BugType& BT = R->getBugType();
1787   Register(&BT);
1788   void *InsertPos;
1789   BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos);
1790
1791   if (!EQ) {
1792     EQ = new BugReportEquivClass(R);
1793     EQClasses.InsertNode(EQ, InsertPos);
1794     EQClassesVector.push_back(EQ);
1795   }
1796   else
1797     EQ->AddReport(R);
1798 }
1799
1800
1801 //===----------------------------------------------------------------------===//
1802 // Emitting reports in equivalence classes.
1803 //===----------------------------------------------------------------------===//
1804
1805 namespace {
1806 struct FRIEC_WLItem {
1807   const ExplodedNode *N;
1808   ExplodedNode::const_succ_iterator I, E;
1809
1810   FRIEC_WLItem(const ExplodedNode *n)
1811   : N(n), I(N->succ_begin()), E(N->succ_end()) {}
1812 };
1813 }
1814
1815 static BugReport *
1816 FindReportInEquivalenceClass(BugReportEquivClass& EQ,
1817                              SmallVectorImpl<BugReport*> &bugReports) {
1818
1819   BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end();
1820   assert(I != E);
1821   BugType& BT = I->getBugType();
1822
1823   // If we don't need to suppress any of the nodes because they are
1824   // post-dominated by a sink, simply add all the nodes in the equivalence class
1825   // to 'Nodes'.  Any of the reports will serve as a "representative" report.
1826   if (!BT.isSuppressOnSink()) {
1827     BugReport *R = I;
1828     for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) {
1829       const ExplodedNode *N = I->getErrorNode();
1830       if (N) {
1831         R = I;
1832         bugReports.push_back(R);
1833       }
1834     }
1835     return R;
1836   }
1837
1838   // For bug reports that should be suppressed when all paths are post-dominated
1839   // by a sink node, iterate through the reports in the equivalence class
1840   // until we find one that isn't post-dominated (if one exists).  We use a
1841   // DFS traversal of the ExplodedGraph to find a non-sink node.  We could write
1842   // this as a recursive function, but we don't want to risk blowing out the
1843   // stack for very long paths.
1844   BugReport *exampleReport = 0;
1845
1846   for (; I != E; ++I) {
1847     const ExplodedNode *errorNode = I->getErrorNode();
1848
1849     if (!errorNode)
1850       continue;
1851     if (errorNode->isSink()) {
1852       llvm_unreachable(
1853            "BugType::isSuppressSink() should not be 'true' for sink end nodes");
1854     }
1855     // No successors?  By definition this nodes isn't post-dominated by a sink.
1856     if (errorNode->succ_empty()) {
1857       bugReports.push_back(I);
1858       if (!exampleReport)
1859         exampleReport = I;
1860       continue;
1861     }
1862
1863     // At this point we know that 'N' is not a sink and it has at least one
1864     // successor.  Use a DFS worklist to find a non-sink end-of-path node.
1865     typedef FRIEC_WLItem WLItem;
1866     typedef SmallVector<WLItem, 10> DFSWorkList;
1867     llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
1868
1869     DFSWorkList WL;
1870     WL.push_back(errorNode);
1871     Visited[errorNode] = 1;
1872
1873     while (!WL.empty()) {
1874       WLItem &WI = WL.back();
1875       assert(!WI.N->succ_empty());
1876
1877       for (; WI.I != WI.E; ++WI.I) {
1878         const ExplodedNode *Succ = *WI.I;
1879         // End-of-path node?
1880         if (Succ->succ_empty()) {
1881           // If we found an end-of-path node that is not a sink.
1882           if (!Succ->isSink()) {
1883             bugReports.push_back(I);
1884             if (!exampleReport)
1885               exampleReport = I;
1886             WL.clear();
1887             break;
1888           }
1889           // Found a sink?  Continue on to the next successor.
1890           continue;
1891         }
1892         // Mark the successor as visited.  If it hasn't been explored,
1893         // enqueue it to the DFS worklist.
1894         unsigned &mark = Visited[Succ];
1895         if (!mark) {
1896           mark = 1;
1897           WL.push_back(Succ);
1898           break;
1899         }
1900       }
1901
1902       // The worklist may have been cleared at this point.  First
1903       // check if it is empty before checking the last item.
1904       if (!WL.empty() && &WL.back() == &WI)
1905         WL.pop_back();
1906     }
1907   }
1908
1909   // ExampleReport will be NULL if all the nodes in the equivalence class
1910   // were post-dominated by sinks.
1911   return exampleReport;
1912 }
1913
1914 //===----------------------------------------------------------------------===//
1915 // DiagnosticCache.  This is a hack to cache analyzer diagnostics.  It
1916 // uses global state, which eventually should go elsewhere.
1917 //===----------------------------------------------------------------------===//
1918 namespace {
1919 class DiagCacheItem : public llvm::FoldingSetNode {
1920   llvm::FoldingSetNodeID ID;
1921 public:
1922   DiagCacheItem(BugReport *R, PathDiagnostic *PD) {
1923     R->Profile(ID);
1924     PD->Profile(ID);
1925   }
1926
1927   void Profile(llvm::FoldingSetNodeID &id) {
1928     id = ID;
1929   }
1930
1931   llvm::FoldingSetNodeID &getID() { return ID; }
1932 };
1933 }
1934
1935 static bool IsCachedDiagnostic(BugReport *R, PathDiagnostic *PD) {
1936   // FIXME: Eventually this diagnostic cache should reside in something
1937   // like AnalysisManager instead of being a static variable.  This is
1938   // really unsafe in the long term.
1939   typedef llvm::FoldingSet<DiagCacheItem> DiagnosticCache;
1940   static DiagnosticCache DC;
1941
1942   void *InsertPos;
1943   DiagCacheItem *Item = new DiagCacheItem(R, PD);
1944
1945   if (DC.FindNodeOrInsertPos(Item->getID(), InsertPos)) {
1946     delete Item;
1947     return true;
1948   }
1949
1950   DC.InsertNode(Item, InsertPos);
1951   return false;
1952 }
1953
1954 void BugReporter::FlushReport(BugReportEquivClass& EQ) {
1955   SmallVector<BugReport*, 10> bugReports;
1956   BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports);
1957   if (!exampleReport)
1958     return;
1959
1960   PathDiagnosticConsumer* PD = getPathDiagnosticConsumer();
1961
1962   // FIXME: Make sure we use the 'R' for the path that was actually used.
1963   // Probably doesn't make a difference in practice.
1964   BugType& BT = exampleReport->getBugType();
1965
1966   OwningPtr<PathDiagnostic>
1967     D(new PathDiagnostic(exampleReport->getDeclWithIssue(),
1968                          exampleReport->getBugType().getName(),
1969                          !PD || PD->useVerboseDescription()
1970                          ? exampleReport->getDescription()
1971                          : exampleReport->getShortDescription(),
1972                          BT.getCategory()));
1973
1974   if (!bugReports.empty())
1975     GeneratePathDiagnostic(*D.get(), bugReports);
1976
1977   // Get the meta data.
1978   const BugReport::ExtraTextList &Meta =
1979                                   exampleReport->getExtraText();
1980   for (BugReport::ExtraTextList::const_iterator i = Meta.begin(),
1981                                                 e = Meta.end(); i != e; ++i) {
1982     D->addMeta(*i);
1983   }
1984
1985   // Emit a summary diagnostic to the regular Diagnostics engine.
1986   BugReport::ranges_iterator Beg, End;
1987   llvm::tie(Beg, End) = exampleReport->getRanges();
1988   DiagnosticsEngine &Diag = getDiagnostic();
1989
1990   if (!IsCachedDiagnostic(exampleReport, D.get())) {
1991     // Search the description for '%', as that will be interpretted as a
1992     // format character by FormatDiagnostics.
1993     StringRef desc = exampleReport->getShortDescription();
1994
1995     SmallString<512> TmpStr;
1996     llvm::raw_svector_ostream Out(TmpStr);
1997     for (StringRef::iterator I=desc.begin(), E=desc.end(); I!=E; ++I) {
1998       if (*I == '%')
1999         Out << "%%";
2000       else
2001         Out << *I;
2002     }
2003
2004     Out.flush();
2005     unsigned ErrorDiag = Diag.getCustomDiagID(DiagnosticsEngine::Warning, TmpStr);
2006
2007     DiagnosticBuilder diagBuilder = Diag.Report(
2008       exampleReport->getLocation(getSourceManager()).asLocation(), ErrorDiag);
2009     for (BugReport::ranges_iterator I = Beg; I != End; ++I)
2010       diagBuilder << *I;
2011   }
2012
2013   // Emit a full diagnostic for the path if we have a PathDiagnosticConsumer.
2014   if (!PD)
2015     return;
2016
2017   if (D->path.empty()) {
2018     PathDiagnosticPiece *piece = new PathDiagnosticEventPiece(
2019                                  exampleReport->getLocation(getSourceManager()),
2020                                  exampleReport->getDescription());
2021     for ( ; Beg != End; ++Beg)
2022       piece->addRange(*Beg);
2023
2024     D->getActivePath().push_back(piece);
2025   }
2026
2027   PD->HandlePathDiagnostic(D.take());
2028 }
2029
2030 void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
2031                                   StringRef name,
2032                                   StringRef category,
2033                                   StringRef str, PathDiagnosticLocation Loc,
2034                                   SourceRange* RBeg, unsigned NumRanges) {
2035
2036   // 'BT' is owned by BugReporter.
2037   BugType *BT = getBugTypeForName(name, category);
2038   BugReport *R = new BugReport(*BT, str, Loc);
2039   R->setDeclWithIssue(DeclWithIssue);
2040   for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg);
2041   EmitReport(R);
2042 }
2043
2044 BugType *BugReporter::getBugTypeForName(StringRef name,
2045                                         StringRef category) {
2046   SmallString<136> fullDesc;
2047   llvm::raw_svector_ostream(fullDesc) << name << ":" << category;
2048   llvm::StringMapEntry<BugType *> &
2049       entry = StrBugTypes.GetOrCreateValue(fullDesc);
2050   BugType *BT = entry.getValue();
2051   if (!BT) {
2052     BT = new BugType(name, category);
2053     entry.setValue(BT);
2054   }
2055   return BT;
2056 }