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