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 #define DEBUG_TYPE "BugReporter"
  16
  17 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  18 #include "clang/AST/ASTContext.h"
  19 #include "clang/AST/DeclObjC.h"
  20 #include "clang/AST/Expr.h"
  21 #include "clang/AST/ParentMap.h"
  22 #include "clang/AST/StmtObjC.h"
  23 #include "clang/Analysis/CFG.h"
  24 #include "clang/Analysis/ProgramPoint.h"
  25 #include "clang/Basic/SourceManager.h"
  26 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  27 #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
  28 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  29 #include "llvm/ADT/DenseMap.h"
  30 #include "llvm/ADT/IntrusiveRefCntPtr.h"
  31 #include "llvm/ADT/OwningPtr.h"
  32 #include "llvm/ADT/STLExtras.h"
  33 #include "llvm/ADT/SmallString.h"
  34 #include "llvm/ADT/Statistic.h"
  35 #include "llvm/Support/raw_ostream.h"
  36 #include <queue>
  37
  38 using namespace clang;
  39 using namespace ento;
  40
  41 STATISTIC(MaxBugClassSize,
  42           "The maximum number of bug reports in the same equivalence class");
  43 STATISTIC(MaxValidBugClassSize,
  44           "The maximum number of bug reports in the same equivalence class "
  45           "where at least one report is valid (not suppressed)");
  46
  47 BugReporterVisitor::~BugReporterVisitor() {}
  48
  49 void BugReporterContext::anchor() {}
  50
  51 //===----------------------------------------------------------------------===//
  52 // Helper routines for walking the ExplodedGraph and fetching statements.
  53 //===----------------------------------------------------------------------===//
  54
  55 static const Stmt *GetPreviousStmt(const ExplodedNode *N) {
  56   for (N = N->getFirstPred(); N; N = N->getFirstPred())
  57     if (const Stmt *S = PathDiagnosticLocation::getStmt(N))
  58       return S;
  59
  60   return 0;
  61 }
  62
  63 static inline const Stmt*
  64 GetCurrentOrPreviousStmt(const ExplodedNode *N) {
  65   if (const Stmt *S = PathDiagnosticLocation::getStmt(N))
  66     return S;
  67
  68   return GetPreviousStmt(N);
  69 }
  70
  71 //===----------------------------------------------------------------------===//
  72 // Diagnostic cleanup.
  73 //===----------------------------------------------------------------------===//
  74
  75 static PathDiagnosticEventPiece *
  76 eventsDescribeSameCondition(PathDiagnosticEventPiece *X,
  77                             PathDiagnosticEventPiece *Y) {
  78   // Prefer diagnostics that come from ConditionBRVisitor over
  79   // those that came from TrackConstraintBRVisitor.
  80   const void *tagPreferred = ConditionBRVisitor::getTag();
  81   const void *tagLesser = TrackConstraintBRVisitor::getTag();
  82
  83   if (X->getLocation() != Y->getLocation())
  84     return 0;
  85
  86   if (X->getTag() == tagPreferred && Y->getTag() == tagLesser)
  87     return X;
  88
  89   if (Y->getTag() == tagPreferred && X->getTag() == tagLesser)
  90     return Y;
  91
  92   return 0;
  93 }
  94
  95 /// An optimization pass over PathPieces that removes redundant diagnostics
  96 /// generated by both ConditionBRVisitor and TrackConstraintBRVisitor.  Both
  97 /// BugReporterVisitors use different methods to generate diagnostics, with
  98 /// one capable of emitting diagnostics in some cases but not in others.  This
  99 /// can lead to redundant diagnostic pieces at the same point in a path.
 100 static void removeRedundantMsgs(PathPieces &path) {
 101   unsigned N = path.size();
 102   if (N < 2)
 103     return;
 104   // NOTE: this loop intentionally is not using an iterator.  Instead, we
 105   // are streaming the path and modifying it in place.  This is done by
 106   // grabbing the front, processing it, and if we decide to keep it append
 107   // it to the end of the path.  The entire path is processed in this way.
 108   for (unsigned i = 0; i < N; ++i) {
 109     IntrusiveRefCntPtr<PathDiagnosticPiece> piece(path.front());
 110     path.pop_front();
 111
 112     switch (piece->getKind()) {
 113       case clang::ento::PathDiagnosticPiece::Call:
 114         removeRedundantMsgs(cast<PathDiagnosticCallPiece>(piece)->path);
 115         break;
 116       case clang::ento::PathDiagnosticPiece::Macro:
 117         removeRedundantMsgs(cast<PathDiagnosticMacroPiece>(piece)->subPieces);
 118         break;
 119       case clang::ento::PathDiagnosticPiece::ControlFlow:
 120         break;
 121       case clang::ento::PathDiagnosticPiece::Event: {
 122         if (i == N-1)
 123           break;
 124
 125         if (PathDiagnosticEventPiece *nextEvent =
 126             dyn_cast<PathDiagnosticEventPiece>(path.front().getPtr())) {
 127           PathDiagnosticEventPiece *event =
 128             cast<PathDiagnosticEventPiece>(piece);
 129           // Check to see if we should keep one of the two pieces.  If we
 130           // come up with a preference, record which piece to keep, and consume
 131           // another piece from the path.
 132           if (PathDiagnosticEventPiece *pieceToKeep =
 133               eventsDescribeSameCondition(event, nextEvent)) {
 134             piece = pieceToKeep;
 135             path.pop_front();
 136             ++i;
 137           }
 138         }
 139         break;
 140       }
 141     }
 142     path.push_back(piece);
 143   }
 144 }
 145
 146 /// A map from PathDiagnosticPiece to the LocationContext of the inlined
 147 /// function call it represents.
 148 typedef llvm::DenseMap<const PathPieces *, const LocationContext *>
 149         LocationContextMap;
 150
 151 /// Recursively scan through a path and prune out calls and macros pieces
 152 /// that aren't needed.  Return true if afterwards the path contains
 153 /// "interesting stuff" which means it shouldn't be pruned from the parent path.
 154 static bool removeUnneededCalls(PathPieces &pieces, BugReport *R,
 155                                 LocationContextMap &LCM) {
 156   bool containsSomethingInteresting = false;
 157   const unsigned N = pieces.size();
 158
 159   for (unsigned i = 0 ; i < N ; ++i) {
 160     // Remove the front piece from the path.  If it is still something we
 161     // want to keep once we are done, we will push it back on the end.
 162     IntrusiveRefCntPtr<PathDiagnosticPiece> piece(pieces.front());
 163     pieces.pop_front();
 164
 165     // Throw away pieces with invalid locations. Note that we can't throw away
 166     // calls just yet because they might have something interesting inside them.
 167     // If so, their locations will be adjusted as necessary later.
 168     if (piece->getKind() != PathDiagnosticPiece::Call &&
 169         piece->getLocation().asLocation().isInvalid())
 170       continue;
 171
 172     switch (piece->getKind()) {
 173       case PathDiagnosticPiece::Call: {
 174         PathDiagnosticCallPiece *call = cast<PathDiagnosticCallPiece>(piece);
 175         // Check if the location context is interesting.
 176         assert(LCM.count(&call->path));
 177         if (R->isInteresting(LCM[&call->path])) {
 178           containsSomethingInteresting = true;
 179           break;
 180         }
 181
 182         if (!removeUnneededCalls(call->path, R, LCM))
 183           continue;
 184
 185         containsSomethingInteresting = true;
 186         break;
 187       }
 188       case PathDiagnosticPiece::Macro: {
 189         PathDiagnosticMacroPiece *macro = cast<PathDiagnosticMacroPiece>(piece);
 190         if (!removeUnneededCalls(macro->subPieces, R, LCM))
 191           continue;
 192         containsSomethingInteresting = true;
 193         break;
 194       }
 195       case PathDiagnosticPiece::Event: {
 196         PathDiagnosticEventPiece *event = cast<PathDiagnosticEventPiece>(piece);
 197
 198         // We never throw away an event, but we do throw it away wholesale
 199         // as part of a path if we throw the entire path away.
 200         containsSomethingInteresting |= !event->isPrunable();
 201         break;
 202       }
 203       case PathDiagnosticPiece::ControlFlow:
 204         break;
 205     }
 206
 207     pieces.push_back(piece);
 208   }
 209
 210   return containsSomethingInteresting;
 211 }
 212
 213 /// Recursively scan through a path and make sure that all call pieces have
 214 /// valid locations. Note that all other pieces with invalid locations should
 215 /// have already been pruned out.
 216 static void adjustCallLocations(PathPieces &Pieces,
 217                                 PathDiagnosticLocation *LastCallLocation = 0) {
 218   for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E; ++I) {
 219     PathDiagnosticCallPiece *Call = dyn_cast<PathDiagnosticCallPiece>(*I);
 220
 221     if (!Call) {
 222       assert((*I)->getLocation().asLocation().isValid());
 223       continue;
 224     }
 225
 226     if (LastCallLocation) {
 227       if (!Call->callEnter.asLocation().isValid() ||
 228           Call->getCaller()->isImplicit())
 229         Call->callEnter = *LastCallLocation;
 230       if (!Call->callReturn.asLocation().isValid() ||
 231           Call->getCaller()->isImplicit())
 232         Call->callReturn = *LastCallLocation;
 233     }
 234
 235     // Recursively clean out the subclass.  Keep this call around if
 236     // it contains any informative diagnostics.
 237     PathDiagnosticLocation *ThisCallLocation;
 238     if (Call->callEnterWithin.asLocation().isValid() &&
 239         !Call->getCallee()->isImplicit())
 240       ThisCallLocation = &Call->callEnterWithin;
 241     else
 242       ThisCallLocation = &Call->callEnter;
 243
 244     assert(ThisCallLocation && "Outermost call has an invalid location");
 245     adjustCallLocations(Call->path, ThisCallLocation);
 246   }
 247 }
 248
 249 //===----------------------------------------------------------------------===//
 250 // PathDiagnosticBuilder and its associated routines and helper objects.
 251 //===----------------------------------------------------------------------===//
 252
 253 namespace {
 254 class NodeMapClosure : public BugReport::NodeResolver {
 255   InterExplodedGraphMap &M;
 256 public:
 257   NodeMapClosure(InterExplodedGraphMap &m) : M(m) {}
 258
 259   const ExplodedNode *getOriginalNode(const ExplodedNode *N) {
 260     return M.lookup(N);
 261   }
 262 };
 263
 264 class PathDiagnosticBuilder : public BugReporterContext {
 265   BugReport *R;
 266   PathDiagnosticConsumer *PDC;
 267   NodeMapClosure NMC;
 268 public:
 269   const LocationContext *LC;
 270
 271   PathDiagnosticBuilder(GRBugReporter &br,
 272                         BugReport *r, InterExplodedGraphMap &Backmap,
 273                         PathDiagnosticConsumer *pdc)
 274     : BugReporterContext(br),
 275       R(r), PDC(pdc), NMC(Backmap), LC(r->getErrorNode()->getLocationContext())
 276   {}
 277
 278   PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N);
 279
 280   PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os,
 281                                             const ExplodedNode *N);
 282
 283   BugReport *getBugReport() { return R; }
 284
 285   Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); }
 286
 287   ParentMap& getParentMap() { return LC->getParentMap(); }
 288
 289   const Stmt *getParent(const Stmt *S) {
 290     return getParentMap().getParent(S);
 291   }
 292
 293   virtual NodeMapClosure& getNodeResolver() { return NMC; }
 294
 295   PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S);
 296
 297   PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const {
 298     return PDC ? PDC->getGenerationScheme() : PathDiagnosticConsumer::Extensive;
 299   }
 300
 301   bool supportsLogicalOpControlFlow() const {
 302     return PDC ? PDC->supportsLogicalOpControlFlow() : true;
 303   }
 304 };
 305 } // end anonymous namespace
 306
 307 PathDiagnosticLocation
 308 PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) {
 309   if (const Stmt *S = PathDiagnosticLocation::getNextStmt(N))
 310     return PathDiagnosticLocation(S, getSourceManager(), LC);
 311
 312   return PathDiagnosticLocation::createDeclEnd(N->getLocationContext(),
 313                                                getSourceManager());
 314 }
 315
 316 PathDiagnosticLocation
 317 PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os,
 318                                           const ExplodedNode *N) {
 319
 320   // Slow, but probably doesn't matter.
 321   if (os.str().empty())
 322     os << ' ';
 323
 324   const PathDiagnosticLocation &Loc = ExecutionContinues(N);
 325
 326   if (Loc.asStmt())
 327     os << "Execution continues on line "
 328        << getSourceManager().getExpansionLineNumber(Loc.asLocation())
 329        << '.';
 330   else {
 331     os << "Execution jumps to the end of the ";
 332     const Decl *D = N->getLocationContext()->getDecl();
 333     if (isa<ObjCMethodDecl>(D))
 334       os << "method";
 335     else if (isa<FunctionDecl>(D))
 336       os << "function";
 337     else {
 338       assert(isa<BlockDecl>(D));
 339       os << "anonymous block";
 340     }
 341     os << '.';
 342   }
 343
 344   return Loc;
 345 }
 346
 347 static bool IsNested(const Stmt *S, ParentMap &PM) {
 348   if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S)))
 349     return true;
 350
 351   const Stmt *Parent = PM.getParentIgnoreParens(S);
 352
 353   if (Parent)
 354     switch (Parent->getStmtClass()) {
 355       case Stmt::ForStmtClass:
 356       case Stmt::DoStmtClass:
 357       case Stmt::WhileStmtClass:
 358         return true;
 359       default:
 360         break;
 361     }
 362
 363   return false;
 364 }
 365
 366 PathDiagnosticLocation
 367 PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) {
 368   assert(S && "Null Stmt *passed to getEnclosingStmtLocation");
 369   ParentMap &P = getParentMap();
 370   SourceManager &SMgr = getSourceManager();
 371
 372   while (IsNested(S, P)) {
 373     const Stmt *Parent = P.getParentIgnoreParens(S);
 374
 375     if (!Parent)
 376       break;
 377
 378     switch (Parent->getStmtClass()) {
 379       case Stmt::BinaryOperatorClass: {
 380         const BinaryOperator *B = cast<BinaryOperator>(Parent);
 381         if (B->isLogicalOp())
 382           return PathDiagnosticLocation(S, SMgr, LC);
 383         break;
 384       }
 385       case Stmt::CompoundStmtClass:
 386       case Stmt::StmtExprClass:
 387         return PathDiagnosticLocation(S, SMgr, LC);
 388       case Stmt::ChooseExprClass:
 389         // Similar to '?' if we are referring to condition, just have the edge
 390         // point to the entire choose expression.
 391         if (cast<ChooseExpr>(Parent)->getCond() == S)
 392           return PathDiagnosticLocation(Parent, SMgr, LC);
 393         else
 394           return PathDiagnosticLocation(S, SMgr, LC);
 395       case Stmt::BinaryConditionalOperatorClass:
 396       case Stmt::ConditionalOperatorClass:
 397         // For '?', if we are referring to condition, just have the edge point
 398         // to the entire '?' expression.
 399         if (cast<AbstractConditionalOperator>(Parent)->getCond() == S)
 400           return PathDiagnosticLocation(Parent, SMgr, LC);
 401         else
 402           return PathDiagnosticLocation(S, SMgr, LC);
 403       case Stmt::DoStmtClass:
 404           return PathDiagnosticLocation(S, SMgr, LC);
 405       case Stmt::ForStmtClass:
 406         if (cast<ForStmt>(Parent)->getBody() == S)
 407           return PathDiagnosticLocation(S, SMgr, LC);
 408         break;
 409       case Stmt::IfStmtClass:
 410         if (cast<IfStmt>(Parent)->getCond() != S)
 411           return PathDiagnosticLocation(S, SMgr, LC);
 412         break;
 413       case Stmt::ObjCForCollectionStmtClass:
 414         if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S)
 415           return PathDiagnosticLocation(S, SMgr, LC);
 416         break;
 417       case Stmt::WhileStmtClass:
 418         if (cast<WhileStmt>(Parent)->getCond() != S)
 419           return PathDiagnosticLocation(S, SMgr, LC);
 420         break;
 421       default:
 422         break;
 423     }
 424
 425     S = Parent;
 426   }
 427
 428   assert(S && "Cannot have null Stmt for PathDiagnosticLocation");
 429
 430   // Special case: DeclStmts can appear in for statement declarations, in which
 431   //  case the ForStmt is the context.
 432   if (isa<DeclStmt>(S)) {
 433     if (const Stmt *Parent = P.getParent(S)) {
 434       switch (Parent->getStmtClass()) {
 435         case Stmt::ForStmtClass:
 436         case Stmt::ObjCForCollectionStmtClass:
 437           return PathDiagnosticLocation(Parent, SMgr, LC);
 438         default:
 439           break;
 440       }
 441     }
 442   }
 443   else if (isa<BinaryOperator>(S)) {
 444     // Special case: the binary operator represents the initialization
 445     // code in a for statement (this can happen when the variable being
 446     // initialized is an old variable.
 447     if (const ForStmt *FS =
 448           dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) {
 449       if (FS->getInit() == S)
 450         return PathDiagnosticLocation(FS, SMgr, LC);
 451     }
 452   }
 453
 454   return PathDiagnosticLocation(S, SMgr, LC);
 455 }
 456
 457 //===----------------------------------------------------------------------===//
 458 // "Visitors only" path diagnostic generation algorithm.
 459 //===----------------------------------------------------------------------===//
 460 static bool GenerateVisitorsOnlyPathDiagnostic(PathDiagnostic &PD,
 461                                                PathDiagnosticBuilder &PDB,
 462                                                const ExplodedNode *N,
 463                                       ArrayRef<BugReporterVisitor *> visitors) {
 464   // All path generation skips the very first node (the error node).
 465   // This is because there is special handling for the end-of-path note.
 466   N = N->getFirstPred();
 467   if (!N)
 468     return true;
 469
 470   BugReport *R = PDB.getBugReport();
 471   while (const ExplodedNode *Pred = N->getFirstPred()) {
 472     for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
 473                                                   E = visitors.end();
 474          I != E; ++I) {
 475       // Visit all the node pairs, but throw the path pieces away.
 476       PathDiagnosticPiece *Piece = (*I)->VisitNode(N, Pred, PDB, *R);
 477       delete Piece;
 478     }
 479
 480     N = Pred;
 481   }
 482
 483   return R->isValid();
 484 }
 485
 486 //===----------------------------------------------------------------------===//
 487 // "Minimal" path diagnostic generation algorithm.
 488 //===----------------------------------------------------------------------===//
 489 typedef std::pair<PathDiagnosticCallPiece*, const ExplodedNode*> StackDiagPair;
 490 typedef SmallVector<StackDiagPair, 6> StackDiagVector;
 491
 492 static void updateStackPiecesWithMessage(PathDiagnosticPiece *P,
 493                                          StackDiagVector &CallStack) {
 494   // If the piece contains a special message, add it to all the call
 495   // pieces on the active stack.
 496   if (PathDiagnosticEventPiece *ep =
 497         dyn_cast<PathDiagnosticEventPiece>(P)) {
 498
 499     if (ep->hasCallStackHint())
 500       for (StackDiagVector::iterator I = CallStack.begin(),
 501                                      E = CallStack.end(); I != E; ++I) {
 502         PathDiagnosticCallPiece *CP = I->first;
 503         const ExplodedNode *N = I->second;
 504         std::string stackMsg = ep->getCallStackMessage(N);
 505
 506         // The last message on the path to final bug is the most important
 507         // one. Since we traverse the path backwards, do not add the message
 508         // if one has been previously added.
 509         if  (!CP->hasCallStackMessage())
 510           CP->setCallStackMessage(stackMsg);
 511       }
 512   }
 513 }
 514
 515 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM);
 516
 517 static bool GenerateMinimalPathDiagnostic(PathDiagnostic& PD,
 518                                           PathDiagnosticBuilder &PDB,
 519                                           const ExplodedNode *N,
 520                                           LocationContextMap &LCM,
 521                                       ArrayRef<BugReporterVisitor *> visitors) {
 522
 523   SourceManager& SMgr = PDB.getSourceManager();
 524   const LocationContext *LC = PDB.LC;
 525   const ExplodedNode *NextNode = N->pred_empty()
 526                                         ? NULL : *(N->pred_begin());
 527
 528   StackDiagVector CallStack;
 529
 530   while (NextNode) {
 531     N = NextNode;
 532     PDB.LC = N->getLocationContext();
 533     NextNode = N->getFirstPred();
 534
 535     ProgramPoint P = N->getLocation();
 536
 537     do {
 538       if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
 539         PathDiagnosticCallPiece *C =
 540             PathDiagnosticCallPiece::construct(N, *CE, SMgr);
 541         // Record the mapping from call piece to LocationContext.
 542         LCM[&C->path] = CE->getCalleeContext();
 543         PD.getActivePath().push_front(C);
 544         PD.pushActivePath(&C->path);
 545         CallStack.push_back(StackDiagPair(C, N));
 546         break;
 547       }
 548
 549       if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
 550         // Flush all locations, and pop the active path.
 551         bool VisitedEntireCall = PD.isWithinCall();
 552         PD.popActivePath();
 553
 554         // Either we just added a bunch of stuff to the top-level path, or
 555         // we have a previous CallExitEnd.  If the former, it means that the
 556         // path terminated within a function call.  We must then take the
 557         // current contents of the active path and place it within
 558         // a new PathDiagnosticCallPiece.
 559         PathDiagnosticCallPiece *C;
 560         if (VisitedEntireCall) {
 561           C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front());
 562         } else {
 563           const Decl *Caller = CE->getLocationContext()->getDecl();
 564           C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller);
 565           // Record the mapping from call piece to LocationContext.
 566           LCM[&C->path] = CE->getCalleeContext();
 567         }
 568
 569         C->setCallee(*CE, SMgr);
 570         if (!CallStack.empty()) {
 571           assert(CallStack.back().first == C);
 572           CallStack.pop_back();
 573         }
 574         break;
 575       }
 576
 577       if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
 578         const CFGBlock *Src = BE->getSrc();
 579         const CFGBlock *Dst = BE->getDst();
 580         const Stmt *T = Src->getTerminator();
 581
 582         if (!T)
 583           break;
 584
 585         PathDiagnosticLocation Start =
 586             PathDiagnosticLocation::createBegin(T, SMgr,
 587                 N->getLocationContext());
 588
 589         switch (T->getStmtClass()) {
 590         default:
 591           break;
 592
 593         case Stmt::GotoStmtClass:
 594         case Stmt::IndirectGotoStmtClass: {
 595           const Stmt *S = PathDiagnosticLocation::getNextStmt(N);
 596
 597           if (!S)
 598             break;
 599
 600           std::string sbuf;
 601           llvm::raw_string_ostream os(sbuf);
 602           const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S);
 603
 604           os << "Control jumps to line "
 605               << End.asLocation().getExpansionLineNumber();
 606           PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 607               Start, End, os.str()));
 608           break;
 609         }
 610
 611         case Stmt::SwitchStmtClass: {
 612           // Figure out what case arm we took.
 613           std::string sbuf;
 614           llvm::raw_string_ostream os(sbuf);
 615
 616           if (const Stmt *S = Dst->getLabel()) {
 617             PathDiagnosticLocation End(S, SMgr, LC);
 618
 619             switch (S->getStmtClass()) {
 620             default:
 621               os << "No cases match in the switch statement. "
 622               "Control jumps to line "
 623               << End.asLocation().getExpansionLineNumber();
 624               break;
 625             case Stmt::DefaultStmtClass:
 626               os << "Control jumps to the 'default' case at line "
 627               << End.asLocation().getExpansionLineNumber();
 628               break;
 629
 630             case Stmt::CaseStmtClass: {
 631               os << "Control jumps to 'case ";
 632               const CaseStmt *Case = cast<CaseStmt>(S);
 633               const Expr *LHS = Case->getLHS()->IgnoreParenCasts();
 634
 635               // Determine if it is an enum.
 636               bool GetRawInt = true;
 637
 638               if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
 639                 // FIXME: Maybe this should be an assertion.  Are there cases
 640                 // were it is not an EnumConstantDecl?
 641                 const EnumConstantDecl *D =
 642                     dyn_cast<EnumConstantDecl>(DR->getDecl());
 643
 644                 if (D) {
 645                   GetRawInt = false;
 646                   os << *D;
 647                 }
 648               }
 649
 650               if (GetRawInt)
 651                 os << LHS->EvaluateKnownConstInt(PDB.getASTContext());
 652
 653               os << ":'  at line "
 654                   << End.asLocation().getExpansionLineNumber();
 655               break;
 656             }
 657             }
 658             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 659                 Start, End, os.str()));
 660           }
 661           else {
 662             os << "'Default' branch taken. ";
 663             const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N);
 664             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 665                 Start, End, os.str()));
 666           }
 667
 668           break;
 669         }
 670
 671         case Stmt::BreakStmtClass:
 672         case Stmt::ContinueStmtClass: {
 673           std::string sbuf;
 674           llvm::raw_string_ostream os(sbuf);
 675           PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
 676           PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 677               Start, End, os.str()));
 678           break;
 679         }
 680
 681         // Determine control-flow for ternary '?'.
 682         case Stmt::BinaryConditionalOperatorClass:
 683         case Stmt::ConditionalOperatorClass: {
 684           std::string sbuf;
 685           llvm::raw_string_ostream os(sbuf);
 686           os << "'?' condition is ";
 687
 688           if (*(Src->succ_begin()+1) == Dst)
 689             os << "false";
 690           else
 691             os << "true";
 692
 693           PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 694
 695           if (const Stmt *S = End.asStmt())
 696             End = PDB.getEnclosingStmtLocation(S);
 697
 698           PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 699               Start, End, os.str()));
 700           break;
 701         }
 702
 703         // Determine control-flow for short-circuited '&&' and '||'.
 704         case Stmt::BinaryOperatorClass: {
 705           if (!PDB.supportsLogicalOpControlFlow())
 706             break;
 707
 708           const BinaryOperator *B = cast<BinaryOperator>(T);
 709           std::string sbuf;
 710           llvm::raw_string_ostream os(sbuf);
 711           os << "Left side of '";
 712
 713           if (B->getOpcode() == BO_LAnd) {
 714             os << "&&" << "' is ";
 715
 716             if (*(Src->succ_begin()+1) == Dst) {
 717               os << "false";
 718               PathDiagnosticLocation End(B->getLHS(), SMgr, LC);
 719               PathDiagnosticLocation Start =
 720                   PathDiagnosticLocation::createOperatorLoc(B, SMgr);
 721               PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 722                   Start, End, os.str()));
 723             }
 724             else {
 725               os << "true";
 726               PathDiagnosticLocation Start(B->getLHS(), SMgr, LC);
 727               PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 728               PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 729                   Start, End, os.str()));
 730             }
 731           }
 732           else {
 733             assert(B->getOpcode() == BO_LOr);
 734             os << "||" << "' is ";
 735
 736             if (*(Src->succ_begin()+1) == Dst) {
 737               os << "false";
 738               PathDiagnosticLocation Start(B->getLHS(), SMgr, LC);
 739               PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 740               PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 741                   Start, End, os.str()));
 742             }
 743             else {
 744               os << "true";
 745               PathDiagnosticLocation End(B->getLHS(), SMgr, LC);
 746               PathDiagnosticLocation Start =
 747                   PathDiagnosticLocation::createOperatorLoc(B, SMgr);
 748               PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 749                   Start, End, os.str()));
 750             }
 751           }
 752
 753           break;
 754         }
 755
 756         case Stmt::DoStmtClass:  {
 757           if (*(Src->succ_begin()) == Dst) {
 758             std::string sbuf;
 759             llvm::raw_string_ostream os(sbuf);
 760
 761             os << "Loop condition is true. ";
 762             PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
 763
 764             if (const Stmt *S = End.asStmt())
 765               End = PDB.getEnclosingStmtLocation(S);
 766
 767             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 768                 Start, End, os.str()));
 769           }
 770           else {
 771             PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 772
 773             if (const Stmt *S = End.asStmt())
 774               End = PDB.getEnclosingStmtLocation(S);
 775
 776             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 777                 Start, End, "Loop condition is false.  Exiting loop"));
 778           }
 779
 780           break;
 781         }
 782
 783         case Stmt::WhileStmtClass:
 784         case Stmt::ForStmtClass: {
 785           if (*(Src->succ_begin()+1) == Dst) {
 786             std::string sbuf;
 787             llvm::raw_string_ostream os(sbuf);
 788
 789             os << "Loop condition is false. ";
 790             PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
 791             if (const Stmt *S = End.asStmt())
 792               End = PDB.getEnclosingStmtLocation(S);
 793
 794             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 795                 Start, End, os.str()));
 796           }
 797           else {
 798             PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 799             if (const Stmt *S = End.asStmt())
 800               End = PDB.getEnclosingStmtLocation(S);
 801
 802             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 803                 Start, End, "Loop condition is true.  Entering loop body"));
 804           }
 805
 806           break;
 807         }
 808
 809         case Stmt::IfStmtClass: {
 810           PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 811
 812           if (const Stmt *S = End.asStmt())
 813             End = PDB.getEnclosingStmtLocation(S);
 814
 815           if (*(Src->succ_begin()+1) == Dst)
 816             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 817                 Start, End, "Taking false branch"));
 818           else
 819             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 820                 Start, End, "Taking true branch"));
 821
 822           break;
 823         }
 824         }
 825       }
 826     } while(0);
 827
 828     if (NextNode) {
 829       // Add diagnostic pieces from custom visitors.
 830       BugReport *R = PDB.getBugReport();
 831       for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
 832                                                     E = visitors.end();
 833            I != E; ++I) {
 834         if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) {
 835           PD.getActivePath().push_front(p);
 836           updateStackPiecesWithMessage(p, CallStack);
 837         }
 838       }
 839     }
 840   }
 841
 842   if (!PDB.getBugReport()->isValid())
 843     return false;
 844
 845   // After constructing the full PathDiagnostic, do a pass over it to compact
 846   // PathDiagnosticPieces that occur within a macro.
 847   CompactPathDiagnostic(PD.getMutablePieces(), PDB.getSourceManager());
 848   return true;
 849 }
 850
 851 //===----------------------------------------------------------------------===//
 852 // "Extensive" PathDiagnostic generation.
 853 //===----------------------------------------------------------------------===//
 854
 855 static bool IsControlFlowExpr(const Stmt *S) {
 856   const Expr *E = dyn_cast<Expr>(S);
 857
 858   if (!E)
 859     return false;
 860
 861   E = E->IgnoreParenCasts();
 862
 863   if (isa<AbstractConditionalOperator>(E))
 864     return true;
 865
 866   if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E))
 867     if (B->isLogicalOp())
 868       return true;
 869
 870   return false;
 871 }
 872
 873 namespace {
 874 class ContextLocation : public PathDiagnosticLocation {
 875   bool IsDead;
 876 public:
 877   ContextLocation(const PathDiagnosticLocation &L, bool isdead = false)
 878     : PathDiagnosticLocation(L), IsDead(isdead) {}
 879
 880   void markDead() { IsDead = true; }
 881   bool isDead() const { return IsDead; }
 882 };
 883
 884 static PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L,
 885                                               const LocationContext *LC,
 886                                               bool firstCharOnly = false) {
 887   if (const Stmt *S = L.asStmt()) {
 888     const Stmt *Original = S;
 889     while (1) {
 890       // Adjust the location for some expressions that are best referenced
 891       // by one of their subexpressions.
 892       switch (S->getStmtClass()) {
 893         default:
 894           break;
 895         case Stmt::ParenExprClass:
 896         case Stmt::GenericSelectionExprClass:
 897           S = cast<Expr>(S)->IgnoreParens();
 898           firstCharOnly = true;
 899           continue;
 900         case Stmt::BinaryConditionalOperatorClass:
 901         case Stmt::ConditionalOperatorClass:
 902           S = cast<AbstractConditionalOperator>(S)->getCond();
 903           firstCharOnly = true;
 904           continue;
 905         case Stmt::ChooseExprClass:
 906           S = cast<ChooseExpr>(S)->getCond();
 907           firstCharOnly = true;
 908           continue;
 909         case Stmt::BinaryOperatorClass:
 910           S = cast<BinaryOperator>(S)->getLHS();
 911           firstCharOnly = true;
 912           continue;
 913       }
 914
 915       break;
 916     }
 917
 918     if (S != Original)
 919       L = PathDiagnosticLocation(S, L.getManager(), LC);
 920   }
 921
 922   if (firstCharOnly)
 923     L  = PathDiagnosticLocation::createSingleLocation(L);
 924
 925   return L;
 926 }
 927
 928 class EdgeBuilder {
 929   std::vector<ContextLocation> CLocs;
 930   typedef std::vector<ContextLocation>::iterator iterator;
 931   PathDiagnostic &PD;
 932   PathDiagnosticBuilder &PDB;
 933   PathDiagnosticLocation PrevLoc;
 934
 935   bool IsConsumedExpr(const PathDiagnosticLocation &L);
 936
 937   bool containsLocation(const PathDiagnosticLocation &Container,
 938                         const PathDiagnosticLocation &Containee);
 939
 940   PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L);
 941
 942
 943
 944   void popLocation() {
 945     if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) {
 946       // For contexts, we only one the first character as the range.
 947       rawAddEdge(cleanUpLocation(CLocs.back(), PDB.LC, true));
 948     }
 949     CLocs.pop_back();
 950   }
 951
 952 public:
 953   EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb)
 954     : PD(pd), PDB(pdb) {
 955
 956       // If the PathDiagnostic already has pieces, add the enclosing statement
 957       // of the first piece as a context as well.
 958       if (!PD.path.empty()) {
 959         PrevLoc = (*PD.path.begin())->getLocation();
 960
 961         if (const Stmt *S = PrevLoc.asStmt())
 962           addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
 963       }
 964   }
 965
 966   ~EdgeBuilder() {
 967     while (!CLocs.empty()) popLocation();
 968
 969     // Finally, add an initial edge from the start location of the first
 970     // statement (if it doesn't already exist).
 971     PathDiagnosticLocation L = PathDiagnosticLocation::createDeclBegin(
 972                                                        PDB.LC,
 973                                                        PDB.getSourceManager());
 974     if (L.isValid())
 975       rawAddEdge(L);
 976   }
 977
 978   void flushLocations() {
 979     while (!CLocs.empty())
 980       popLocation();
 981     PrevLoc = PathDiagnosticLocation();
 982   }
 983
 984   void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false,
 985                bool IsPostJump = false);
 986
 987   void rawAddEdge(PathDiagnosticLocation NewLoc);
 988
 989   void addContext(const Stmt *S);
 990   void addContext(const PathDiagnosticLocation &L);
 991   void addExtendedContext(const Stmt *S);
 992 };
 993 } // end anonymous namespace
 994
 995
 996 PathDiagnosticLocation
 997 EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) {
 998   if (const Stmt *S = L.asStmt()) {
 999     if (IsControlFlowExpr(S))
1000       return L;
1001
1002     return PDB.getEnclosingStmtLocation(S);
1003   }
1004
1005   return L;
1006 }
1007
1008 bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container,
1009                                    const PathDiagnosticLocation &Containee) {
1010
1011   if (Container == Containee)
1012     return true;
1013
1014   if (Container.asDecl())
1015     return true;
1016
1017   if (const Stmt *S = Containee.asStmt())
1018     if (const Stmt *ContainerS = Container.asStmt()) {
1019       while (S) {
1020         if (S == ContainerS)
1021           return true;
1022         S = PDB.getParent(S);
1023       }
1024       return false;
1025     }
1026
1027   // Less accurate: compare using source ranges.
1028   SourceRange ContainerR = Container.asRange();
1029   SourceRange ContaineeR = Containee.asRange();
1030
1031   SourceManager &SM = PDB.getSourceManager();
1032   SourceLocation ContainerRBeg = SM.getExpansionLoc(ContainerR.getBegin());
1033   SourceLocation ContainerREnd = SM.getExpansionLoc(ContainerR.getEnd());
1034   SourceLocation ContaineeRBeg = SM.getExpansionLoc(ContaineeR.getBegin());
1035   SourceLocation ContaineeREnd = SM.getExpansionLoc(ContaineeR.getEnd());
1036
1037   unsigned ContainerBegLine = SM.getExpansionLineNumber(ContainerRBeg);
1038   unsigned ContainerEndLine = SM.getExpansionLineNumber(ContainerREnd);
1039   unsigned ContaineeBegLine = SM.getExpansionLineNumber(ContaineeRBeg);
1040   unsigned ContaineeEndLine = SM.getExpansionLineNumber(ContaineeREnd);
1041
1042   assert(ContainerBegLine <= ContainerEndLine);
1043   assert(ContaineeBegLine <= ContaineeEndLine);
1044
1045   return (ContainerBegLine <= ContaineeBegLine &&
1046           ContainerEndLine >= ContaineeEndLine &&
1047           (ContainerBegLine != ContaineeBegLine ||
1048            SM.getExpansionColumnNumber(ContainerRBeg) <=
1049            SM.getExpansionColumnNumber(ContaineeRBeg)) &&
1050           (ContainerEndLine != ContaineeEndLine ||
1051            SM.getExpansionColumnNumber(ContainerREnd) >=
1052            SM.getExpansionColumnNumber(ContaineeREnd)));
1053 }
1054
1055 void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) {
1056   if (!PrevLoc.isValid()) {
1057     PrevLoc = NewLoc;
1058     return;
1059   }
1060
1061   const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc, PDB.LC);
1062   const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc, PDB.LC);
1063
1064   if (PrevLocClean.asLocation().isInvalid()) {
1065     PrevLoc = NewLoc;
1066     return;
1067   }
1068
1069   if (NewLocClean.asLocation() == PrevLocClean.asLocation())
1070     return;
1071
1072   // FIXME: Ignore intra-macro edges for now.
1073   if (NewLocClean.asLocation().getExpansionLoc() ==
1074       PrevLocClean.asLocation().getExpansionLoc())
1075     return;
1076
1077   PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean));
1078   PrevLoc = NewLoc;
1079 }
1080
1081 void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd,
1082                           bool IsPostJump) {
1083
1084   if (!alwaysAdd && NewLoc.asLocation().isMacroID())
1085     return;
1086
1087   const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc);
1088
1089   while (!CLocs.empty()) {
1090     ContextLocation &TopContextLoc = CLocs.back();
1091
1092     // Is the top location context the same as the one for the new location?
1093     if (TopContextLoc == CLoc) {
1094       if (alwaysAdd) {
1095         if (IsConsumedExpr(TopContextLoc))
1096           TopContextLoc.markDead();
1097
1098         rawAddEdge(NewLoc);
1099       }
1100
1101       if (IsPostJump)
1102         TopContextLoc.markDead();
1103       return;
1104     }
1105
1106     if (containsLocation(TopContextLoc, CLoc)) {
1107       if (alwaysAdd) {
1108         rawAddEdge(NewLoc);
1109
1110         if (IsConsumedExpr(CLoc)) {
1111           CLocs.push_back(ContextLocation(CLoc, /*IsDead=*/true));
1112           return;
1113         }
1114       }
1115
1116       CLocs.push_back(ContextLocation(CLoc, /*IsDead=*/IsPostJump));
1117       return;
1118     }
1119
1120     // Context does not contain the location.  Flush it.
1121     popLocation();
1122   }
1123
1124   // If we reach here, there is no enclosing context.  Just add the edge.
1125   rawAddEdge(NewLoc);
1126 }
1127
1128 bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) {
1129   if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt()))
1130     return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X);
1131
1132   return false;
1133 }
1134
1135 void EdgeBuilder::addExtendedContext(const Stmt *S) {
1136   if (!S)
1137     return;
1138
1139   const Stmt *Parent = PDB.getParent(S);
1140   while (Parent) {
1141     if (isa<CompoundStmt>(Parent))
1142       Parent = PDB.getParent(Parent);
1143     else
1144       break;
1145   }
1146
1147   if (Parent) {
1148     switch (Parent->getStmtClass()) {
1149       case Stmt::DoStmtClass:
1150       case Stmt::ObjCAtSynchronizedStmtClass:
1151         addContext(Parent);
1152       default:
1153         break;
1154     }
1155   }
1156
1157   addContext(S);
1158 }
1159
1160 void EdgeBuilder::addContext(const Stmt *S) {
1161   if (!S)
1162     return;
1163
1164   PathDiagnosticLocation L(S, PDB.getSourceManager(), PDB.LC);
1165   addContext(L);
1166 }
1167
1168 void EdgeBuilder::addContext(const PathDiagnosticLocation &L) {
1169   while (!CLocs.empty()) {
1170     const PathDiagnosticLocation &TopContextLoc = CLocs.back();
1171
1172     // Is the top location context the same as the one for the new location?
1173     if (TopContextLoc == L)
1174       return;
1175
1176     if (containsLocation(TopContextLoc, L)) {
1177       CLocs.push_back(L);
1178       return;
1179     }
1180
1181     // Context does not contain the location.  Flush it.
1182     popLocation();
1183   }
1184
1185   CLocs.push_back(L);
1186 }
1187
1188 // Cone-of-influence: support the reverse propagation of "interesting" symbols
1189 // and values by tracing interesting calculations backwards through evaluated
1190 // expressions along a path.  This is probably overly complicated, but the idea
1191 // is that if an expression computed an "interesting" value, the child
1192 // expressions are are also likely to be "interesting" as well (which then
1193 // propagates to the values they in turn compute).  This reverse propagation
1194 // is needed to track interesting correlations across function call boundaries,
1195 // where formal arguments bind to actual arguments, etc.  This is also needed
1196 // because the constraint solver sometimes simplifies certain symbolic values
1197 // into constants when appropriate, and this complicates reasoning about
1198 // interesting values.
1199 typedef llvm::DenseSet<const Expr *> InterestingExprs;
1200
1201 static void reversePropagateIntererstingSymbols(BugReport &R,
1202                                                 InterestingExprs &IE,
1203                                                 const ProgramState *State,
1204                                                 const Expr *Ex,
1205                                                 const LocationContext *LCtx) {
1206   SVal V = State->getSVal(Ex, LCtx);
1207   if (!(R.isInteresting(V) || IE.count(Ex)))
1208     return;
1209
1210   switch (Ex->getStmtClass()) {
1211     default:
1212       if (!isa<CastExpr>(Ex))
1213         break;
1214       // Fall through.
1215     case Stmt::BinaryOperatorClass:
1216     case Stmt::UnaryOperatorClass: {
1217       for (Stmt::const_child_iterator CI = Ex->child_begin(),
1218             CE = Ex->child_end();
1219             CI != CE; ++CI) {
1220         if (const Expr *child = dyn_cast_or_null<Expr>(*CI)) {
1221           IE.insert(child);
1222           SVal ChildV = State->getSVal(child, LCtx);
1223           R.markInteresting(ChildV);
1224         }
1225         break;
1226       }
1227     }
1228   }
1229
1230   R.markInteresting(V);
1231 }
1232
1233 static void reversePropagateInterestingSymbols(BugReport &R,
1234                                                InterestingExprs &IE,
1235                                                const ProgramState *State,
1236                                                const LocationContext *CalleeCtx,
1237                                                const LocationContext *CallerCtx)
1238 {
1239   // FIXME: Handle non-CallExpr-based CallEvents.
1240   const StackFrameContext *Callee = CalleeCtx->getCurrentStackFrame();
1241   const Stmt *CallSite = Callee->getCallSite();
1242   if (const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite)) {
1243     if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CalleeCtx->getDecl())) {
1244       FunctionDecl::param_const_iterator PI = FD->param_begin(),
1245                                          PE = FD->param_end();
1246       CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
1247       for (; AI != AE && PI != PE; ++AI, ++PI) {
1248         if (const Expr *ArgE = *AI) {
1249           if (const ParmVarDecl *PD = *PI) {
1250             Loc LV = State->getLValue(PD, CalleeCtx);
1251             if (R.isInteresting(LV) || R.isInteresting(State->getRawSVal(LV)))
1252               IE.insert(ArgE);
1253           }
1254         }
1255       }
1256     }
1257   }
1258 }
1259
1260 //===----------------------------------------------------------------------===//
1261 // Functions for determining if a loop was executed 0 times.
1262 //===----------------------------------------------------------------------===//
1263
1264 /// Return true if the terminator is a loop and the destination is the
1265 /// false branch.
1266 static bool isLoopJumpPastBody(const Stmt *Term, const BlockEdge *BE) {
1267   switch (Term->getStmtClass()) {
1268     case Stmt::ForStmtClass:
1269     case Stmt::WhileStmtClass:
1270     case Stmt::ObjCForCollectionStmtClass:
1271       break;
1272     default:
1273       // Note that we intentionally do not include do..while here.
1274       return false;
1275   }
1276
1277   // Did we take the false branch?
1278   const CFGBlock *Src = BE->getSrc();
1279   assert(Src->succ_size() == 2);
1280   return (*(Src->succ_begin()+1) == BE->getDst());
1281 }
1282
1283 static bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS) {
1284   while (SubS) {
1285     if (SubS == S)
1286       return true;
1287     SubS = PM.getParent(SubS);
1288   }
1289   return false;
1290 }
1291
1292 static const Stmt *getStmtBeforeCond(ParentMap &PM, const Stmt *Term,
1293                                      const ExplodedNode *N) {
1294   while (N) {
1295     Optional<StmtPoint> SP = N->getLocation().getAs<StmtPoint>();
1296     if (SP) {
1297       const Stmt *S = SP->getStmt();
1298       if (!isContainedByStmt(PM, Term, S))
1299         return S;
1300     }
1301     N = N->getFirstPred();
1302   }
1303   return 0;
1304 }
1305
1306 static bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term) {
1307   const Stmt *LoopBody = 0;
1308   switch (Term->getStmtClass()) {
1309     case Stmt::ForStmtClass: {
1310       const ForStmt *FS = cast<ForStmt>(Term);
1311       if (isContainedByStmt(PM, FS->getInc(), S))
1312         return true;
1313       LoopBody = FS->getBody();
1314       break;
1315     }
1316     case Stmt::ObjCForCollectionStmtClass: {
1317       const ObjCForCollectionStmt *FC = cast<ObjCForCollectionStmt>(Term);
1318       LoopBody = FC->getBody();
1319       break;
1320     }
1321     case Stmt::WhileStmtClass:
1322       LoopBody = cast<WhileStmt>(Term)->getBody();
1323       break;
1324     default:
1325       return false;
1326   }
1327   return isContainedByStmt(PM, LoopBody, S);
1328 }
1329
1330 //===----------------------------------------------------------------------===//
1331 // Top-level logic for generating extensive path diagnostics.
1332 //===----------------------------------------------------------------------===//
1333
1334 static bool GenerateExtensivePathDiagnostic(PathDiagnostic& PD,
1335                                             PathDiagnosticBuilder &PDB,
1336                                             const ExplodedNode *N,
1337                                             LocationContextMap &LCM,
1338                                       ArrayRef<BugReporterVisitor *> visitors) {
1339   EdgeBuilder EB(PD, PDB);
1340   const SourceManager& SM = PDB.getSourceManager();
1341   StackDiagVector CallStack;
1342   InterestingExprs IE;
1343
1344   const ExplodedNode *NextNode = N->pred_empty() ? NULL : *(N->pred_begin());
1345   while (NextNode) {
1346     N = NextNode;
1347     NextNode = N->getFirstPred();
1348     ProgramPoint P = N->getLocation();
1349
1350     do {
1351       if (Optional<PostStmt> PS = P.getAs<PostStmt>()) {
1352         if (const Expr *Ex = PS->getStmtAs<Expr>())
1353           reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1354                                               N->getState().getPtr(), Ex,
1355                                               N->getLocationContext());
1356       }
1357
1358       if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
1359         const Stmt *S = CE->getCalleeContext()->getCallSite();
1360         if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) {
1361             reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1362                                                 N->getState().getPtr(), Ex,
1363                                                 N->getLocationContext());
1364         }
1365
1366         PathDiagnosticCallPiece *C =
1367           PathDiagnosticCallPiece::construct(N, *CE, SM);
1368         LCM[&C->path] = CE->getCalleeContext();
1369
1370         EB.addEdge(C->callReturn, /*AlwaysAdd=*/true, /*IsPostJump=*/true);
1371         EB.flushLocations();
1372
1373         PD.getActivePath().push_front(C);
1374         PD.pushActivePath(&C->path);
1375         CallStack.push_back(StackDiagPair(C, N));
1376         break;
1377       }
1378
1379       // Pop the call hierarchy if we are done walking the contents
1380       // of a function call.
1381       if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
1382         // Add an edge to the start of the function.
1383         const Decl *D = CE->getCalleeContext()->getDecl();
1384         PathDiagnosticLocation pos =
1385           PathDiagnosticLocation::createBegin(D, SM);
1386         EB.addEdge(pos);
1387
1388         // Flush all locations, and pop the active path.
1389         bool VisitedEntireCall = PD.isWithinCall();
1390         EB.flushLocations();
1391         PD.popActivePath();
1392         PDB.LC = N->getLocationContext();
1393
1394         // Either we just added a bunch of stuff to the top-level path, or
1395         // we have a previous CallExitEnd.  If the former, it means that the
1396         // path terminated within a function call.  We must then take the
1397         // current contents of the active path and place it within
1398         // a new PathDiagnosticCallPiece.
1399         PathDiagnosticCallPiece *C;
1400         if (VisitedEntireCall) {
1401           C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front());
1402         } else {
1403           const Decl *Caller = CE->getLocationContext()->getDecl();
1404           C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller);
1405           LCM[&C->path] = CE->getCalleeContext();
1406         }
1407
1408         C->setCallee(*CE, SM);
1409         EB.addContext(C->getLocation());
1410
1411         if (!CallStack.empty()) {
1412           assert(CallStack.back().first == C);
1413           CallStack.pop_back();
1414         }
1415         break;
1416       }
1417
1418       // Note that is important that we update the LocationContext
1419       // after looking at CallExits.  CallExit basically adds an
1420       // edge in the *caller*, so we don't want to update the LocationContext
1421       // too soon.
1422       PDB.LC = N->getLocationContext();
1423
1424       // Block edges.
1425       if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
1426         // Does this represent entering a call?  If so, look at propagating
1427         // interesting symbols across call boundaries.
1428         if (NextNode) {
1429           const LocationContext *CallerCtx = NextNode->getLocationContext();
1430           const LocationContext *CalleeCtx = PDB.LC;
1431           if (CallerCtx != CalleeCtx) {
1432             reversePropagateInterestingSymbols(*PDB.getBugReport(), IE,
1433                                                N->getState().getPtr(),
1434                                                CalleeCtx, CallerCtx);
1435           }
1436         }
1437
1438         // Are we jumping to the head of a loop?  Add a special diagnostic.
1439         if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) {
1440           PathDiagnosticLocation L(Loop, SM, PDB.LC);
1441           const CompoundStmt *CS = NULL;
1442
1443           if (const ForStmt *FS = dyn_cast<ForStmt>(Loop))
1444             CS = dyn_cast<CompoundStmt>(FS->getBody());
1445           else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop))
1446             CS = dyn_cast<CompoundStmt>(WS->getBody());
1447
1448           PathDiagnosticEventPiece *p =
1449             new PathDiagnosticEventPiece(L,
1450                                         "Looping back to the head of the loop");
1451           p->setPrunable(true);
1452
1453           EB.addEdge(p->getLocation(), true);
1454           PD.getActivePath().push_front(p);
1455
1456           if (CS) {
1457             PathDiagnosticLocation BL =
1458               PathDiagnosticLocation::createEndBrace(CS, SM);
1459             EB.addEdge(BL);
1460           }
1461         }
1462
1463         const CFGBlock *BSrc = BE->getSrc();
1464         ParentMap &PM = PDB.getParentMap();
1465
1466         if (const Stmt *Term = BSrc->getTerminator()) {
1467           // Are we jumping past the loop body without ever executing the
1468           // loop (because the condition was false)?
1469           if (isLoopJumpPastBody(Term, &*BE) &&
1470               !isInLoopBody(PM,
1471                             getStmtBeforeCond(PM,
1472                                               BSrc->getTerminatorCondition(),
1473                                               N),
1474                             Term)) {
1475             PathDiagnosticLocation L(Term, SM, PDB.LC);
1476             PathDiagnosticEventPiece *PE =
1477                 new PathDiagnosticEventPiece(L, "Loop body executed 0 times");
1478             PE->setPrunable(true);
1479
1480             EB.addEdge(PE->getLocation(), true);
1481             PD.getActivePath().push_front(PE);
1482           }
1483
1484           // In any case, add the terminator as the current statement
1485           // context for control edges.
1486           EB.addContext(Term);
1487         }
1488
1489         break;
1490       }
1491
1492       if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
1493         Optional<CFGElement> First = BE->getFirstElement();
1494         if (Optional<CFGStmt> S = First ? First->getAs<CFGStmt>() : None) {
1495           const Stmt *stmt = S->getStmt();
1496           if (IsControlFlowExpr(stmt)) {
1497             // Add the proper context for '&&', '||', and '?'.
1498             EB.addContext(stmt);
1499           }
1500           else
1501             EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt());
1502         }
1503
1504         break;
1505       }
1506
1507
1508     } while (0);
1509
1510     if (!NextNode)
1511       continue;
1512
1513     // Add pieces from custom visitors.
1514     BugReport *R = PDB.getBugReport();
1515     for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
1516                                                   E = visitors.end();
1517          I != E; ++I) {
1518       if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) {
1519         const PathDiagnosticLocation &Loc = p->getLocation();
1520         EB.addEdge(Loc, true);
1521         PD.getActivePath().push_front(p);
1522         updateStackPiecesWithMessage(p, CallStack);
1523
1524         if (const Stmt *S = Loc.asStmt())
1525           EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1526       }
1527     }
1528   }
1529
1530   return PDB.getBugReport()->isValid();
1531 }
1532
1533 /// \brief Adds a sanitized control-flow diagnostic edge to a path.
1534 static void addEdgeToPath(PathPieces &path,
1535                           PathDiagnosticLocation &PrevLoc,
1536                           PathDiagnosticLocation NewLoc,
1537                           const LocationContext *LC) {
1538   if (!NewLoc.isValid())
1539     return;
1540
1541   SourceLocation NewLocL = NewLoc.asLocation();
1542   if (NewLocL.isInvalid() || NewLocL.isMacroID())
1543     return;
1544
1545   if (!PrevLoc.isValid()) {
1546     PrevLoc = NewLoc;
1547     return;
1548   }
1549
1550   // FIXME: ignore intra-macro edges for now.
1551   if (NewLoc.asLocation().getExpansionLoc() ==
1552       PrevLoc.asLocation().getExpansionLoc())
1553     return;
1554
1555   path.push_front(new PathDiagnosticControlFlowPiece(NewLoc,
1556                                                      PrevLoc));
1557   PrevLoc = NewLoc;
1558 }
1559
1560 static bool
1561 GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD,
1562                                          PathDiagnosticBuilder &PDB,
1563                                          const ExplodedNode *N,
1564                                          LocationContextMap &LCM,
1565                                       ArrayRef<BugReporterVisitor *> visitors) {
1566
1567   BugReport *report = PDB.getBugReport();
1568   const SourceManager& SM = PDB.getSourceManager();
1569   StackDiagVector CallStack;
1570   InterestingExprs IE;
1571
1572   // Record the last location for a given visited stack frame.
1573   llvm::DenseMap<const StackFrameContext *, PathDiagnosticLocation>
1574     PrevLocMap;
1575
1576   const ExplodedNode *NextNode = N->getFirstPred();
1577   while (NextNode) {
1578     N = NextNode;
1579     NextNode = N->getFirstPred();
1580     ProgramPoint P = N->getLocation();
1581     const LocationContext *LC = N->getLocationContext();
1582     assert(!LCM[&PD.getActivePath()] || LCM[&PD.getActivePath()] == LC);
1583     LCM[&PD.getActivePath()] = LC;
1584     PathDiagnosticLocation &PrevLoc = PrevLocMap[LC->getCurrentStackFrame()];
1585
1586     do {
1587       if (Optional<PostStmt> PS = P.getAs<PostStmt>()) {
1588         // For expressions, make sure we propagate the
1589         // interesting symbols correctly.
1590         if (const Expr *Ex = PS->getStmtAs<Expr>())
1591           reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1592                                               N->getState().getPtr(), Ex,
1593                                               N->getLocationContext());
1594
1595         PathDiagnosticLocation L =
1596           PathDiagnosticLocation(PS->getStmt(), SM, LC);
1597         addEdgeToPath(PD.getActivePath(), PrevLoc, L, LC);
1598         break;
1599       }
1600
1601       // Have we encountered an exit from a function call?
1602       if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
1603         const Stmt *S = CE->getCalleeContext()->getCallSite();
1604         // Propagate the interesting symbols accordingly.
1605         if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) {
1606           reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1607                                               N->getState().getPtr(), Ex,
1608                                               N->getLocationContext());
1609         }
1610
1611         // We are descending into a call (backwards).  Construct
1612         // a new call piece to contain the path pieces for that call.
1613         PathDiagnosticCallPiece *C =
1614           PathDiagnosticCallPiece::construct(N, *CE, SM);
1615
1616         // Record the location context for this call piece.
1617         LCM[&C->path] = CE->getCalleeContext();
1618
1619         // Add the edge to the return site.
1620         addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, LC);
1621
1622         // Make the contents of the call the active path for now.
1623         PD.pushActivePath(&C->path);
1624         CallStack.push_back(StackDiagPair(C, N));
1625         break;
1626       }
1627
1628       // Have we encountered an entrance to a call?  It may be
1629       // the case that we have not encountered a matching
1630       // call exit before this point.  This means that the path
1631       // terminated within the call itself.
1632       if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
1633         // Add an edge to the start of the function.
1634         const Decl *D = CE->getCalleeContext()->getDecl();
1635         addEdgeToPath(PD.getActivePath(), PrevLoc,
1636                       PathDiagnosticLocation::createBegin(D, SM), LC);
1637
1638         // Did we visit an entire call?
1639         bool VisitedEntireCall = PD.isWithinCall();
1640         PD.popActivePath();
1641
1642         PathDiagnosticCallPiece *C;
1643         if (VisitedEntireCall) {
1644           C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front());
1645         } else {
1646           const Decl *Caller = CE->getLocationContext()->getDecl();
1647           C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller);
1648           LCM[&C->path] = CE->getCalleeContext();
1649         }
1650         C->setCallee(*CE, SM);
1651
1652         if (!CallStack.empty()) {
1653           assert(CallStack.back().first == C);
1654           CallStack.pop_back();
1655         }
1656         break;
1657       }
1658
1659       // Block edges.
1660       if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
1661         // Does this represent entering a call?  If so, look at propagating
1662         // interesting symbols across call boundaries.
1663         if (NextNode) {
1664           const LocationContext *CallerCtx = NextNode->getLocationContext();
1665           const LocationContext *CalleeCtx = PDB.LC;
1666           if (CallerCtx != CalleeCtx) {
1667             reversePropagateInterestingSymbols(*PDB.getBugReport(), IE,
1668                                                N->getState().getPtr(),
1669                                                CalleeCtx, CallerCtx);
1670           }
1671         }
1672
1673         // Are we jumping to the head of a loop?  Add a special diagnostic.
1674         if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) {
1675           PathDiagnosticLocation L(Loop, SM, PDB.LC);
1676           const CompoundStmt *CS = NULL;
1677
1678           if (const ForStmt *FS = dyn_cast<ForStmt>(Loop))
1679             CS = dyn_cast<CompoundStmt>(FS->getBody());
1680           else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop))
1681             CS = dyn_cast<CompoundStmt>(WS->getBody());
1682
1683           PathDiagnosticEventPiece *p =
1684             new PathDiagnosticEventPiece(L, "Looping back to the head "
1685                                             "of the loop");
1686           p->setPrunable(true);
1687
1688           addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), LC);
1689           PD.getActivePath().push_front(p);
1690
1691           if (CS) {
1692             addEdgeToPath(PD.getActivePath(), PrevLoc,
1693                           PathDiagnosticLocation::createEndBrace(CS, SM), LC);
1694           }
1695         }
1696
1697         const CFGBlock *BSrc = BE->getSrc();
1698         ParentMap &PM = PDB.getParentMap();
1699
1700         if (const Stmt *Term = BSrc->getTerminator()) {
1701           // Are we jumping past the loop body without ever executing the
1702           // loop (because the condition was false)?
1703           if (isLoopJumpPastBody(Term, &*BE) &&
1704               !isInLoopBody(PM,
1705                             getStmtBeforeCond(PM,
1706                                               BSrc->getTerminatorCondition(),
1707                                               N),
1708                             Term))
1709           {
1710             PathDiagnosticLocation L(Term, SM, PDB.LC);
1711             PathDiagnosticEventPiece *PE =
1712               new PathDiagnosticEventPiece(L, "Loop body executed 0 times");
1713             PE->setPrunable(true);
1714             addEdgeToPath(PD.getActivePath(), PrevLoc,
1715                           PE->getLocation(), LC);
1716             PD.getActivePath().push_front(PE);
1717           }
1718         }
1719         break;
1720       }
1721     } while (0);
1722
1723     if (!NextNode)
1724       continue;
1725
1726     // Add pieces from custom visitors.
1727     for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
1728          E = visitors.end();
1729          I != E; ++I) {
1730       if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *report)) {
1731         addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), LC);
1732         PD.getActivePath().push_front(p);
1733         updateStackPiecesWithMessage(p, CallStack);
1734       }
1735     }
1736   }
1737
1738   return report->isValid();
1739 }
1740
1741 const Stmt *getLocStmt(PathDiagnosticLocation L) {
1742   if (!L.isValid())
1743     return 0;
1744   return L.asStmt();
1745 }
1746
1747 const Stmt *getStmtParent(const Stmt *S, ParentMap &PM) {
1748   if (!S)
1749     return 0;
1750   return PM.getParentIgnoreParens(S);
1751 }
1752
1753 #if 0
1754 static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) {
1755   // Note that we intentionally to do not handle || and && here.
1756   switch (S->getStmtClass()) {
1757     case Stmt::ForStmtClass:
1758       return cast<ForStmt>(S)->getCond() == Cond;
1759     case Stmt::WhileStmtClass:
1760       return cast<WhileStmt>(S)->getCond() == Cond;
1761     case Stmt::DoStmtClass:
1762       return cast<DoStmt>(S)->getCond() == Cond;
1763     case Stmt::ChooseExprClass:
1764       return cast<ChooseExpr>(S)->getCond() == Cond;
1765     case Stmt::IndirectGotoStmtClass:
1766       return cast<IndirectGotoStmt>(S)->getTarget() == Cond;
1767     case Stmt::SwitchStmtClass:
1768       return cast<SwitchStmt>(S)->getCond() == Cond;
1769     case Stmt::BinaryConditionalOperatorClass:
1770       return cast<BinaryConditionalOperator>(S)->getCond() == Cond;
1771     case Stmt::ConditionalOperatorClass:
1772       return cast<ConditionalOperator>(S)->getCond() == Cond;
1773     case Stmt::ObjCForCollectionStmtClass:
1774       return cast<ObjCForCollectionStmt>(S)->getElement() == Cond;
1775     default:
1776       return false;
1777   }
1778 }
1779 #endif
1780
1781 typedef llvm::DenseSet<const PathDiagnosticControlFlowPiece *>
1782         ControlFlowBarrierSet;
1783
1784 typedef llvm::DenseSet<const PathDiagnosticCallPiece *>
1785         OptimizedCallsSet;
1786
1787 static bool isBarrier(ControlFlowBarrierSet &CFBS,
1788                       const PathDiagnosticControlFlowPiece *P) {
1789   return CFBS.count(P);
1790 }
1791
1792 static bool optimizeEdges(PathPieces &path, SourceManager &SM,
1793                           ControlFlowBarrierSet &CFBS,
1794                           OptimizedCallsSet &OCS,
1795                           LocationContextMap &LCM) {
1796   bool hasChanges = false;
1797   const LocationContext *LC = LCM[&path];
1798   assert(LC);
1799   bool isFirst = true;
1800
1801   for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) {
1802     bool wasFirst = isFirst;
1803     isFirst = false;
1804
1805     // Optimize subpaths.
1806     if (PathDiagnosticCallPiece *CallI = dyn_cast<PathDiagnosticCallPiece>(*I)){
1807       // Record the fact that a call has been optimized so we only do the
1808       // effort once.
1809       if (!OCS.count(CallI)) {
1810         while (optimizeEdges(CallI->path, SM, CFBS, OCS, LCM)) {}
1811         OCS.insert(CallI);
1812       }
1813       ++I;
1814       continue;
1815     }
1816
1817     // Pattern match the current piece and its successor.
1818     PathDiagnosticControlFlowPiece *PieceI =
1819       dyn_cast<PathDiagnosticControlFlowPiece>(*I);
1820
1821     if (!PieceI) {
1822       ++I;
1823       continue;
1824     }
1825
1826     ParentMap &PM = LC->getParentMap();
1827     const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
1828     const Stmt *s1End   = getLocStmt(PieceI->getEndLocation());
1829     const Stmt *level1 = getStmtParent(s1Start, PM);
1830     const Stmt *level2 = getStmtParent(s1End, PM);
1831
1832     if (wasFirst) {
1833 #if 0
1834       // Apply the "first edge" case for Rule V. here.
1835       if (s1Start && level1 && isConditionForTerminator(level1, s1Start)) {
1836         PathDiagnosticLocation NewLoc(level2, SM, LC);
1837         PieceI->setStartLocation(NewLoc);
1838         CFBS.insert(PieceI);
1839         return true;
1840       }
1841 #endif
1842       // Apply the "first edge" case for Rule III. here.
1843       if (!isBarrier(CFBS, PieceI) &&
1844           level1 && level2 && level2 == PM.getParent(level1)) {
1845         path.erase(I);
1846         // Since we are erasing the current edge at the start of the
1847         // path, just return now so we start analyzing the start of the path
1848         // again.
1849         return true;
1850       }
1851     }
1852
1853     PathPieces::iterator NextI = I; ++NextI;
1854     if (NextI == E)
1855       break;
1856
1857     PathDiagnosticControlFlowPiece *PieceNextI =
1858       dyn_cast<PathDiagnosticControlFlowPiece>(*NextI);
1859
1860     if (!PieceNextI) {
1861       ++I;
1862       continue;
1863     }
1864
1865     const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation());
1866     const Stmt *s2End   = getLocStmt(PieceNextI->getEndLocation());
1867     const Stmt *level3 = getStmtParent(s2Start, PM);
1868     const Stmt *level4 = getStmtParent(s2End, PM);
1869
1870     // Rule I.
1871     //
1872     // If we have two consecutive control edges whose end/begin locations
1873     // are at the same level (e.g. statements or top-level expressions within
1874     // a compound statement, or siblings share a single ancestor expression),
1875     // then merge them if they have no interesting intermediate event.
1876     //
1877     // For example:
1878     //
1879     // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common
1880     // parent is '1'.  Here 'x.y.z' represents the hierarchy of statements.
1881     //
1882     // NOTE: this will be limited later in cases where we add barriers
1883     // to prevent this optimization.
1884     //
1885     if (level1 && level1 == level2 && level1 == level3 && level1 == level4) {
1886       PieceI->setEndLocation(PieceNextI->getEndLocation());
1887       path.erase(NextI);
1888       hasChanges = true;
1889       continue;
1890     }
1891
1892     // Rule II.
1893     //
1894     // If we have two consecutive control edges where we decend to a
1895     // subexpression and then pop out merge them.
1896     //
1897     // NOTE: this will be limited later in cases where we add barriers
1898     // to prevent this optimization.
1899     //
1900     // For example:
1901     //
1902     // (1.1 -> 1.1.1) -> (1.1.1 -> 1.2) becomes (1.1 -> 1.2).
1903     if (level1 && level2 &&
1904         level1 == level4 &&
1905         level2 == level3 && PM.getParentIgnoreParens(level2) == level1) {
1906       PieceI->setEndLocation(PieceNextI->getEndLocation());
1907       path.erase(NextI);
1908       hasChanges = true;
1909       continue;
1910     }
1911
1912     // Rule III.
1913     //
1914     // Eliminate unnecessary edges where we descend to a subexpression from
1915     // a statement at the same level as our parent.
1916     //
1917     // NOTE: this will be limited later in cases where we add barriers
1918     // to prevent this optimization.
1919     //
1920     // For example:
1921     //
1922     // (1.1 -> 1.1.1) -> (1.1.1 -> X) becomes (1.1 -> X).
1923     //
1924     if (level1 && level2 && level1 == PM.getParentIgnoreParens(level2)) {
1925       PieceI->setEndLocation(PieceNextI->getEndLocation());
1926       path.erase(NextI);
1927       hasChanges = true;
1928       continue;
1929     }
1930
1931     // Rule IV.
1932     //
1933     // Eliminate unnecessary edges where we ascend from a subexpression to
1934     // a statement at the same level as our parent.
1935     //
1936     // NOTE: this will be limited later in cases where we add barriers
1937     // to prevent this optimization.
1938     //
1939     // For example:
1940     //
1941     // (X -> 1.1.1) -> (1.1.1 -> 1.1) becomes (X -> 1.1).
1942     // [first edge] (1.1.1 -> 1.1) -> eliminate
1943     //
1944     if (level2 && level4 && level2 == level3 && level4 == PM.getParent(level2)){
1945       PieceI->setEndLocation(PieceNextI->getEndLocation());
1946       path.erase(NextI);
1947       hasChanges = true;
1948       continue;
1949     }
1950 #if 0
1951     // Rule V.
1952     //
1953     // Replace terminator conditions with terminators when the condition
1954     // itself has no control-flow.
1955     //
1956     // For example:
1957     //
1958     // (X -> condition) -> (condition -> Y) becomes (X -> term) -> (term -> Y)
1959     // [first edge] (condition -> Y) becomes (term -> Y)
1960     //
1961     // This applies to 'if', 'for', 'while', 'do .. while', 'switch'...
1962     //
1963     if (!isBarrier(CFBS, PieceNextI) &&
1964         s1End && s1End == s2Start && level2) {
1965       if (isConditionForTerminator(level2, s1End)) {
1966         PathDiagnosticLocation NewLoc(level2, SM, LC);
1967         PieceI->setEndLocation(NewLoc);
1968         PieceNextI->setStartLocation(NewLoc);
1969         CFBS.insert(PieceI);
1970         hasChanges = true;
1971         continue;
1972       }
1973
1974     }
1975 #endif
1976
1977     // No changes at this index?  Move to the next one.
1978     ++I;
1979   }
1980
1981   // No changes.
1982   return hasChanges;
1983 }
1984
1985 //===----------------------------------------------------------------------===//
1986 // Methods for BugType and subclasses.
1987 //===----------------------------------------------------------------------===//
1988 BugType::~BugType() { }
1989
1990 void BugType::FlushReports(BugReporter &BR) {}
1991
1992 void BuiltinBug::anchor() {}
1993
1994 //===----------------------------------------------------------------------===//
1995 // Methods for BugReport and subclasses.
1996 //===----------------------------------------------------------------------===//
1997
1998 void BugReport::NodeResolver::anchor() {}
1999
2000 void BugReport::addVisitor(BugReporterVisitor* visitor) {
2001   if (!visitor)
2002     return;
2003
2004   llvm::FoldingSetNodeID ID;
2005   visitor->Profile(ID);
2006   void *InsertPos;
2007
2008   if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) {
2009     delete visitor;
2010     return;
2011   }
2012
2013   CallbacksSet.InsertNode(visitor, InsertPos);
2014   Callbacks.push_back(visitor);
2015   ++ConfigurationChangeToken;
2016 }
2017
2018 BugReport::~BugReport() {
2019   for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I) {
2020     delete *I;
2021   }
2022   while (!interestingSymbols.empty()) {
2023     popInterestingSymbolsAndRegions();
2024   }
2025 }
2026
2027 const Decl *BugReport::getDeclWithIssue() const {
2028   if (DeclWithIssue)
2029     return DeclWithIssue;
2030
2031   const ExplodedNode *N = getErrorNode();
2032   if (!N)
2033     return 0;
2034
2035   const LocationContext *LC = N->getLocationContext();
2036   return LC->getCurrentStackFrame()->getDecl();
2037 }
2038
2039 void BugReport::Profile(llvm::FoldingSetNodeID& hash) const {
2040   hash.AddPointer(&BT);
2041   hash.AddString(Description);
2042   PathDiagnosticLocation UL = getUniqueingLocation();
2043   if (UL.isValid()) {
2044     UL.Profile(hash);
2045   } else if (Location.isValid()) {
2046     Location.Profile(hash);
2047   } else {
2048     assert(ErrorNode);
2049     hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode));
2050   }
2051
2052   for (SmallVectorImpl<SourceRange>::const_iterator I =
2053       Ranges.begin(), E = Ranges.end(); I != E; ++I) {
2054     const SourceRange range = *I;
2055     if (!range.isValid())
2056       continue;
2057     hash.AddInteger(range.getBegin().getRawEncoding());
2058     hash.AddInteger(range.getEnd().getRawEncoding());
2059   }
2060 }
2061
2062 void BugReport::markInteresting(SymbolRef sym) {
2063   if (!sym)
2064     return;
2065
2066   // If the symbol wasn't already in our set, note a configuration change.
2067   if (getInterestingSymbols().insert(sym).second)
2068     ++ConfigurationChangeToken;
2069
2070   if (const SymbolMetadata *meta = dyn_cast<SymbolMetadata>(sym))
2071     getInterestingRegions().insert(meta->getRegion());
2072 }
2073
2074 void BugReport::markInteresting(const MemRegion *R) {
2075   if (!R)
2076     return;
2077
2078   // If the base region wasn't already in our set, note a configuration change.
2079   R = R->getBaseRegion();
2080   if (getInterestingRegions().insert(R).second)
2081     ++ConfigurationChangeToken;
2082
2083   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
2084     getInterestingSymbols().insert(SR->getSymbol());
2085 }
2086
2087 void BugReport::markInteresting(SVal V) {
2088   markInteresting(V.getAsRegion());
2089   markInteresting(V.getAsSymbol());
2090 }
2091
2092 void BugReport::markInteresting(const LocationContext *LC) {
2093   if (!LC)
2094     return;
2095   InterestingLocationContexts.insert(LC);
2096 }
2097
2098 bool BugReport::isInteresting(SVal V) {
2099   return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol());
2100 }
2101
2102 bool BugReport::isInteresting(SymbolRef sym) {
2103   if (!sym)
2104     return false;
2105   // We don't currently consider metadata symbols to be interesting
2106   // even if we know their region is interesting. Is that correct behavior?
2107   return getInterestingSymbols().count(sym);
2108 }
2109
2110 bool BugReport::isInteresting(const MemRegion *R) {
2111   if (!R)
2112     return false;
2113   R = R->getBaseRegion();
2114   bool b = getInterestingRegions().count(R);
2115   if (b)
2116     return true;
2117   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
2118     return getInterestingSymbols().count(SR->getSymbol());
2119   return false;
2120 }
2121
2122 bool BugReport::isInteresting(const LocationContext *LC) {
2123   if (!LC)
2124     return false;
2125   return InterestingLocationContexts.count(LC);
2126 }
2127
2128 void BugReport::lazyInitializeInterestingSets() {
2129   if (interestingSymbols.empty()) {
2130     interestingSymbols.push_back(new Symbols());
2131     interestingRegions.push_back(new Regions());
2132   }
2133 }
2134
2135 BugReport::Symbols &BugReport::getInterestingSymbols() {
2136   lazyInitializeInterestingSets();
2137   return *interestingSymbols.back();
2138 }
2139
2140 BugReport::Regions &BugReport::getInterestingRegions() {
2141   lazyInitializeInterestingSets();
2142   return *interestingRegions.back();
2143 }
2144
2145 void BugReport::pushInterestingSymbolsAndRegions() {
2146   interestingSymbols.push_back(new Symbols(getInterestingSymbols()));
2147   interestingRegions.push_back(new Regions(getInterestingRegions()));
2148 }
2149
2150 void BugReport::popInterestingSymbolsAndRegions() {
2151   delete interestingSymbols.back();
2152   interestingSymbols.pop_back();
2153   delete interestingRegions.back();
2154   interestingRegions.pop_back();
2155 }
2156
2157 const Stmt *BugReport::getStmt() const {
2158   if (!ErrorNode)
2159     return 0;
2160
2161   ProgramPoint ProgP = ErrorNode->getLocation();
2162   const Stmt *S = NULL;
2163
2164   if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) {
2165     CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
2166     if (BE->getBlock() == &Exit)
2167       S = GetPreviousStmt(ErrorNode);
2168   }
2169   if (!S)
2170     S = PathDiagnosticLocation::getStmt(ErrorNode);
2171
2172   return S;
2173 }
2174
2175 std::pair<BugReport::ranges_iterator, BugReport::ranges_iterator>
2176 BugReport::getRanges() {
2177     // If no custom ranges, add the range of the statement corresponding to
2178     // the error node.
2179     if (Ranges.empty()) {
2180       if (const Expr *E = dyn_cast_or_null<Expr>(getStmt()))
2181         addRange(E->getSourceRange());
2182       else
2183         return std::make_pair(ranges_iterator(), ranges_iterator());
2184     }
2185
2186     // User-specified absence of range info.
2187     if (Ranges.size() == 1 && !Ranges.begin()->isValid())
2188       return std::make_pair(ranges_iterator(), ranges_iterator());
2189
2190     return std::make_pair(Ranges.begin(), Ranges.end());
2191 }
2192
2193 PathDiagnosticLocation BugReport::getLocation(const SourceManager &SM) const {
2194   if (ErrorNode) {
2195     assert(!Location.isValid() &&
2196      "Either Location or ErrorNode should be specified but not both.");
2197     return PathDiagnosticLocation::createEndOfPath(ErrorNode, SM);
2198   } else {
2199     assert(Location.isValid());
2200     return Location;
2201   }
2202
2203   return PathDiagnosticLocation();
2204 }
2205
2206 //===----------------------------------------------------------------------===//
2207 // Methods for BugReporter and subclasses.
2208 //===----------------------------------------------------------------------===//
2209
2210 BugReportEquivClass::~BugReportEquivClass() { }
2211 GRBugReporter::~GRBugReporter() { }
2212 BugReporterData::~BugReporterData() {}
2213
2214 ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
2215
2216 ProgramStateManager&
2217 GRBugReporter::getStateManager() { return Eng.getStateManager(); }
2218
2219 BugReporter::~BugReporter() {
2220   FlushReports();
2221
2222   // Free the bug reports we are tracking.
2223   typedef std::vector<BugReportEquivClass *> ContTy;
2224   for (ContTy::iterator I = EQClassesVector.begin(), E = EQClassesVector.end();
2225        I != E; ++I) {
2226     delete *I;
2227   }
2228 }
2229
2230 void BugReporter::FlushReports() {
2231   if (BugTypes.isEmpty())
2232     return;
2233
2234   // First flush the warnings for each BugType.  This may end up creating new
2235   // warnings and new BugTypes.
2236   // FIXME: Only NSErrorChecker needs BugType's FlushReports.
2237   // Turn NSErrorChecker into a proper checker and remove this.
2238   SmallVector<const BugType*, 16> bugTypes;
2239   for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I)
2240     bugTypes.push_back(*I);
2241   for (SmallVector<const BugType*, 16>::iterator
2242          I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I)
2243     const_cast<BugType*>(*I)->FlushReports(*this);
2244
2245   // We need to flush reports in deterministic order to ensure the order
2246   // of the reports is consistent between runs.
2247   typedef std::vector<BugReportEquivClass *> ContVecTy;
2248   for (ContVecTy::iterator EI=EQClassesVector.begin(), EE=EQClassesVector.end();
2249        EI != EE; ++EI){
2250     BugReportEquivClass& EQ = **EI;
2251     FlushReport(EQ);
2252   }
2253
2254   // BugReporter owns and deletes only BugTypes created implicitly through
2255   // EmitBasicReport.
2256   // FIXME: There are leaks from checkers that assume that the BugTypes they
2257   // create will be destroyed by the BugReporter.
2258   for (llvm::StringMap<BugType*>::iterator
2259          I = StrBugTypes.begin(), E = StrBugTypes.end(); I != E; ++I)
2260     delete I->second;
2261
2262   // Remove all references to the BugType objects.
2263   BugTypes = F.getEmptySet();
2264 }
2265
2266 //===----------------------------------------------------------------------===//
2267 // PathDiagnostics generation.
2268 //===----------------------------------------------------------------------===//
2269
2270 namespace {
2271 /// A wrapper around a report graph, which contains only a single path, and its
2272 /// node maps.
2273 class ReportGraph {
2274 public:
2275   InterExplodedGraphMap BackMap;
2276   OwningPtr<ExplodedGraph> Graph;
2277   const ExplodedNode *ErrorNode;
2278   size_t Index;
2279 };
2280
2281 /// A wrapper around a trimmed graph and its node maps.
2282 class TrimmedGraph {
2283   InterExplodedGraphMap InverseMap;
2284
2285   typedef llvm::DenseMap<const ExplodedNode *, unsigned> PriorityMapTy;
2286   PriorityMapTy PriorityMap;
2287
2288   typedef std::pair<const ExplodedNode *, size_t> NodeIndexPair;
2289   SmallVector<NodeIndexPair, 32> ReportNodes;
2290
2291   OwningPtr<ExplodedGraph> G;
2292
2293   /// A helper class for sorting ExplodedNodes by priority.
2294   template <bool Descending>
2295   class PriorityCompare {
2296     const PriorityMapTy &PriorityMap;
2297
2298   public:
2299     PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {}
2300
2301     bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const {
2302       PriorityMapTy::const_iterator LI = PriorityMap.find(LHS);
2303       PriorityMapTy::const_iterator RI = PriorityMap.find(RHS);
2304       PriorityMapTy::const_iterator E = PriorityMap.end();
2305
2306       if (LI == E)
2307         return Descending;
2308       if (RI == E)
2309         return !Descending;
2310
2311       return Descending ? LI->second > RI->second
2312                         : LI->second < RI->second;
2313     }
2314
2315     bool operator()(const NodeIndexPair &LHS, const NodeIndexPair &RHS) const {
2316       return (*this)(LHS.first, RHS.first);
2317     }
2318   };
2319
2320 public:
2321   TrimmedGraph(const ExplodedGraph *OriginalGraph,
2322                ArrayRef<const ExplodedNode *> Nodes);
2323
2324   bool popNextReportGraph(ReportGraph &GraphWrapper);
2325 };
2326 }
2327
2328 TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph,
2329                            ArrayRef<const ExplodedNode *> Nodes) {
2330   // The trimmed graph is created in the body of the constructor to ensure
2331   // that the DenseMaps have been initialized already.
2332   InterExplodedGraphMap ForwardMap;
2333   G.reset(OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap));
2334
2335   // Find the (first) error node in the trimmed graph.  We just need to consult
2336   // the node map which maps from nodes in the original graph to nodes
2337   // in the new graph.
2338   llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes;
2339
2340   for (unsigned i = 0, count = Nodes.size(); i < count; ++i) {
2341     if (const ExplodedNode *NewNode = ForwardMap.lookup(Nodes[i])) {
2342       ReportNodes.push_back(std::make_pair(NewNode, i));
2343       RemainingNodes.insert(NewNode);
2344     }
2345   }
2346
2347   assert(!RemainingNodes.empty() && "No error node found in the trimmed graph");
2348
2349   // Perform a forward BFS to find all the shortest paths.
2350   std::queue<const ExplodedNode *> WS;
2351
2352   assert(G->num_roots() == 1);
2353   WS.push(*G->roots_begin());
2354   unsigned Priority = 0;
2355
2356   while (!WS.empty()) {
2357     const ExplodedNode *Node = WS.front();
2358     WS.pop();
2359
2360     PriorityMapTy::iterator PriorityEntry;
2361     bool IsNew;
2362     llvm::tie(PriorityEntry, IsNew) =
2363       PriorityMap.insert(std::make_pair(Node, Priority));
2364     ++Priority;
2365
2366     if (!IsNew) {
2367       assert(PriorityEntry->second <= Priority);
2368       continue;
2369     }
2370
2371     if (RemainingNodes.erase(Node))
2372       if (RemainingNodes.empty())
2373         break;
2374
2375     for (ExplodedNode::const_pred_iterator I = Node->succ_begin(),
2376                                            E = Node->succ_end();
2377          I != E; ++I)
2378       WS.push(*I);
2379   }
2380
2381   // Sort the error paths from longest to shortest.
2382   std::sort(ReportNodes.begin(), ReportNodes.end(),
2383             PriorityCompare<true>(PriorityMap));
2384 }
2385
2386 bool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) {
2387   if (ReportNodes.empty())
2388     return false;
2389
2390   const ExplodedNode *OrigN;
2391   llvm::tie(OrigN, GraphWrapper.Index) = ReportNodes.pop_back_val();
2392   assert(PriorityMap.find(OrigN) != PriorityMap.end() &&
2393          "error node not accessible from root");
2394
2395   // Create a new graph with a single path.  This is the graph
2396   // that will be returned to the caller.
2397   ExplodedGraph *GNew = new ExplodedGraph();
2398   GraphWrapper.Graph.reset(GNew);
2399   GraphWrapper.BackMap.clear();
2400
2401   // Now walk from the error node up the BFS path, always taking the
2402   // predeccessor with the lowest number.
2403   ExplodedNode *Succ = 0;
2404   while (true) {
2405     // Create the equivalent node in the new graph with the same state
2406     // and location.
2407     ExplodedNode *NewN = GNew->getNode(OrigN->getLocation(), OrigN->getState(),
2408                                        OrigN->isSink());
2409
2410     // Store the mapping to the original node.
2411     InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN);
2412     assert(IMitr != InverseMap.end() && "No mapping to original node.");
2413     GraphWrapper.BackMap[NewN] = IMitr->second;
2414
2415     // Link up the new node with the previous node.
2416     if (Succ)
2417       Succ->addPredecessor(NewN, *GNew);
2418     else
2419       GraphWrapper.ErrorNode = NewN;
2420
2421     Succ = NewN;
2422
2423     // Are we at the final node?
2424     if (OrigN->pred_empty()) {
2425       GNew->addRoot(NewN);
2426       break;
2427     }
2428
2429     // Find the next predeccessor node.  We choose the node that is marked
2430     // with the lowest BFS number.
2431     OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(),
2432                           PriorityCompare<false>(PriorityMap));
2433   }
2434
2435   return true;
2436 }
2437
2438
2439 /// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
2440 ///  and collapses PathDiagosticPieces that are expanded by macros.
2441 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) {
2442   typedef std::vector<std::pair<IntrusiveRefCntPtr<PathDiagnosticMacroPiece>,
2443                                 SourceLocation> > MacroStackTy;
2444
2445   typedef std::vector<IntrusiveRefCntPtr<PathDiagnosticPiece> >
2446           PiecesTy;
2447
2448   MacroStackTy MacroStack;
2449   PiecesTy Pieces;
2450
2451   for (PathPieces::const_iterator I = path.begin(), E = path.end();
2452        I!=E; ++I) {
2453
2454     PathDiagnosticPiece *piece = I->getPtr();
2455
2456     // Recursively compact calls.
2457     if (PathDiagnosticCallPiece *call=dyn_cast<PathDiagnosticCallPiece>(piece)){
2458       CompactPathDiagnostic(call->path, SM);
2459     }
2460
2461     // Get the location of the PathDiagnosticPiece.
2462     const FullSourceLoc Loc = piece->getLocation().asLocation();
2463
2464     // Determine the instantiation location, which is the location we group
2465     // related PathDiagnosticPieces.
2466     SourceLocation InstantiationLoc = Loc.isMacroID() ?
2467                                       SM.getExpansionLoc(Loc) :
2468                                       SourceLocation();
2469
2470     if (Loc.isFileID()) {
2471       MacroStack.clear();
2472       Pieces.push_back(piece);
2473       continue;
2474     }
2475
2476     assert(Loc.isMacroID());
2477
2478     // Is the PathDiagnosticPiece within the same macro group?
2479     if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
2480       MacroStack.back().first->subPieces.push_back(piece);
2481       continue;
2482     }
2483
2484     // We aren't in the same group.  Are we descending into a new macro
2485     // or are part of an old one?
2486     IntrusiveRefCntPtr<PathDiagnosticMacroPiece> MacroGroup;
2487
2488     SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
2489                                           SM.getExpansionLoc(Loc) :
2490                                           SourceLocation();
2491
2492     // Walk the entire macro stack.
2493     while (!MacroStack.empty()) {
2494       if (InstantiationLoc == MacroStack.back().second) {
2495         MacroGroup = MacroStack.back().first;
2496         break;
2497       }
2498
2499       if (ParentInstantiationLoc == MacroStack.back().second) {
2500         MacroGroup = MacroStack.back().first;
2501         break;
2502       }
2503
2504       MacroStack.pop_back();
2505     }
2506
2507     if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
2508       // Create a new macro group and add it to the stack.
2509       PathDiagnosticMacroPiece *NewGroup =
2510         new PathDiagnosticMacroPiece(
2511           PathDiagnosticLocation::createSingleLocation(piece->getLocation()));
2512
2513       if (MacroGroup)
2514         MacroGroup->subPieces.push_back(NewGroup);
2515       else {
2516         assert(InstantiationLoc.isFileID());
2517         Pieces.push_back(NewGroup);
2518       }
2519
2520       MacroGroup = NewGroup;
2521       MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
2522     }
2523
2524     // Finally, add the PathDiagnosticPiece to the group.
2525     MacroGroup->subPieces.push_back(piece);
2526   }
2527
2528   // Now take the pieces and construct a new PathDiagnostic.
2529   path.clear();
2530
2531   for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I)
2532     path.push_back(*I);
2533 }
2534
2535 bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD,
2536                                            PathDiagnosticConsumer &PC,
2537                                            ArrayRef<BugReport *> &bugReports) {
2538   assert(!bugReports.empty());
2539
2540   bool HasValid = false;
2541   bool HasInvalid = false;
2542   SmallVector<const ExplodedNode *, 32> errorNodes;
2543   for (ArrayRef<BugReport*>::iterator I = bugReports.begin(),
2544                                       E = bugReports.end(); I != E; ++I) {
2545     if ((*I)->isValid()) {
2546       HasValid = true;
2547       errorNodes.push_back((*I)->getErrorNode());
2548     } else {
2549       // Keep the errorNodes list in sync with the bugReports list.
2550       HasInvalid = true;
2551       errorNodes.push_back(0);
2552     }
2553   }
2554
2555   // If all the reports have been marked invalid by a previous path generation,
2556   // we're done.
2557   if (!HasValid)
2558     return false;
2559
2560   typedef PathDiagnosticConsumer::PathGenerationScheme PathGenerationScheme;
2561   PathGenerationScheme ActiveScheme = PC.getGenerationScheme();
2562
2563   if (ActiveScheme == PathDiagnosticConsumer::Extensive) {
2564     AnalyzerOptions &options = getEngine().getAnalysisManager().options;
2565     if (options.getBooleanOption("path-diagnostics-alternate", false)) {
2566       ActiveScheme = PathDiagnosticConsumer::AlternateExtensive;
2567     }
2568   }
2569
2570   TrimmedGraph TrimG(&getGraph(), errorNodes);
2571   ReportGraph ErrorGraph;
2572
2573   while (TrimG.popNextReportGraph(ErrorGraph)) {
2574     // Find the BugReport with the original location.
2575     assert(ErrorGraph.Index < bugReports.size());
2576     BugReport *R = bugReports[ErrorGraph.Index];
2577     assert(R && "No original report found for sliced graph.");
2578     assert(R->isValid() && "Report selected by trimmed graph marked invalid.");
2579
2580     // Start building the path diagnostic...
2581     PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, &PC);
2582     const ExplodedNode *N = ErrorGraph.ErrorNode;
2583
2584     // Register additional node visitors.
2585     R->addVisitor(new NilReceiverBRVisitor());
2586     R->addVisitor(new ConditionBRVisitor());
2587     R->addVisitor(new LikelyFalsePositiveSuppressionBRVisitor());
2588
2589     BugReport::VisitorList visitors;
2590     unsigned origReportConfigToken, finalReportConfigToken;
2591     LocationContextMap LCM;
2592
2593     // While generating diagnostics, it's possible the visitors will decide
2594     // new symbols and regions are interesting, or add other visitors based on
2595     // the information they find. If they do, we need to regenerate the path
2596     // based on our new report configuration.
2597     do {
2598       // Get a clean copy of all the visitors.
2599       for (BugReport::visitor_iterator I = R->visitor_begin(),
2600                                        E = R->visitor_end(); I != E; ++I)
2601         visitors.push_back((*I)->clone());
2602
2603       // Clear out the active path from any previous work.
2604       PD.resetPath();
2605       origReportConfigToken = R->getConfigurationChangeToken();
2606
2607       // Generate the very last diagnostic piece - the piece is visible before
2608       // the trace is expanded.
2609       PathDiagnosticPiece *LastPiece = 0;
2610       for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end();
2611           I != E; ++I) {
2612         if (PathDiagnosticPiece *Piece = (*I)->getEndPath(PDB, N, *R)) {
2613           assert (!LastPiece &&
2614               "There can only be one final piece in a diagnostic.");
2615           LastPiece = Piece;
2616         }
2617       }
2618
2619       if (ActiveScheme != PathDiagnosticConsumer::None) {
2620         if (!LastPiece)
2621           LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R);
2622         assert(LastPiece);
2623         PD.setEndOfPath(LastPiece);
2624       }
2625
2626       // Make sure we get a clean location context map so we don't
2627       // hold onto old mappings.
2628       LCM.clear();
2629
2630       switch (ActiveScheme) {
2631       case PathDiagnosticConsumer::AlternateExtensive:
2632         GenerateAlternateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors);
2633         break;
2634       case PathDiagnosticConsumer::Extensive:
2635         GenerateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors);
2636         break;
2637       case PathDiagnosticConsumer::Minimal:
2638         GenerateMinimalPathDiagnostic(PD, PDB, N, LCM, visitors);
2639         break;
2640       case PathDiagnosticConsumer::None:
2641         GenerateVisitorsOnlyPathDiagnostic(PD, PDB, N, visitors);
2642         break;
2643       }
2644
2645       // Clean up the visitors we used.
2646       llvm::DeleteContainerPointers(visitors);
2647
2648       // Did anything change while generating this path?
2649       finalReportConfigToken = R->getConfigurationChangeToken();
2650     } while (finalReportConfigToken != origReportConfigToken);
2651
2652     if (!R->isValid())
2653       continue;
2654
2655     // Finally, prune the diagnostic path of uninteresting stuff.
2656     if (!PD.path.empty()) {
2657       // Remove messages that are basically the same.
2658       removeRedundantMsgs(PD.getMutablePieces());
2659
2660       if (R->shouldPrunePath() &&
2661           getEngine().getAnalysisManager().options.shouldPrunePaths()) {
2662         bool stillHasNotes = removeUnneededCalls(PD.getMutablePieces(), R, LCM);
2663         assert(stillHasNotes);
2664         (void)stillHasNotes;
2665       }
2666
2667       adjustCallLocations(PD.getMutablePieces());
2668
2669       if (ActiveScheme == PathDiagnosticConsumer::AlternateExtensive) {
2670         ControlFlowBarrierSet CFBS;
2671         OptimizedCallsSet OCS;
2672         while (optimizeEdges(PD.getMutablePieces(), getSourceManager(), CFBS,
2673                              OCS, LCM)) {}
2674       }
2675     }
2676
2677     // We found a report and didn't suppress it.
2678     return true;
2679   }
2680
2681   // We suppressed all the reports in this equivalence class.
2682   assert(!HasInvalid && "Inconsistent suppression");
2683   (void)HasInvalid;
2684   return false;
2685 }
2686
2687 void BugReporter::Register(BugType *BT) {
2688   BugTypes = F.add(BugTypes, BT);
2689 }
2690
2691 void BugReporter::emitReport(BugReport* R) {
2692   // Compute the bug report's hash to determine its equivalence class.
2693   llvm::FoldingSetNodeID ID;
2694   R->Profile(ID);
2695
2696   // Lookup the equivance class.  If there isn't one, create it.
2697   BugType& BT = R->getBugType();
2698   Register(&BT);
2699   void *InsertPos;
2700   BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos);
2701
2702   if (!EQ) {
2703     EQ = new BugReportEquivClass(R);
2704     EQClasses.InsertNode(EQ, InsertPos);
2705     EQClassesVector.push_back(EQ);
2706   }
2707   else
2708     EQ->AddReport(R);
2709 }
2710
2711
2712 //===----------------------------------------------------------------------===//
2713 // Emitting reports in equivalence classes.
2714 //===----------------------------------------------------------------------===//
2715
2716 namespace {
2717 struct FRIEC_WLItem {
2718   const ExplodedNode *N;
2719   ExplodedNode::const_succ_iterator I, E;
2720
2721   FRIEC_WLItem(const ExplodedNode *n)
2722   : N(n), I(N->succ_begin()), E(N->succ_end()) {}
2723 };
2724 }
2725
2726 static BugReport *
2727 FindReportInEquivalenceClass(BugReportEquivClass& EQ,
2728                              SmallVectorImpl<BugReport*> &bugReports) {
2729
2730   BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end();
2731   assert(I != E);
2732   BugType& BT = I->getBugType();
2733
2734   // If we don't need to suppress any of the nodes because they are
2735   // post-dominated by a sink, simply add all the nodes in the equivalence class
2736   // to 'Nodes'.  Any of the reports will serve as a "representative" report.
2737   if (!BT.isSuppressOnSink()) {
2738     BugReport *R = I;
2739     for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) {
2740       const ExplodedNode *N = I->getErrorNode();
2741       if (N) {
2742         R = I;
2743         bugReports.push_back(R);
2744       }
2745     }
2746     return R;
2747   }
2748
2749   // For bug reports that should be suppressed when all paths are post-dominated
2750   // by a sink node, iterate through the reports in the equivalence class
2751   // until we find one that isn't post-dominated (if one exists).  We use a
2752   // DFS traversal of the ExplodedGraph to find a non-sink node.  We could write
2753   // this as a recursive function, but we don't want to risk blowing out the
2754   // stack for very long paths.
2755   BugReport *exampleReport = 0;
2756
2757   for (; I != E; ++I) {
2758     const ExplodedNode *errorNode = I->getErrorNode();
2759
2760     if (!errorNode)
2761       continue;
2762     if (errorNode->isSink()) {
2763       llvm_unreachable(
2764            "BugType::isSuppressSink() should not be 'true' for sink end nodes");
2765     }
2766     // No successors?  By definition this nodes isn't post-dominated by a sink.
2767     if (errorNode->succ_empty()) {
2768       bugReports.push_back(I);
2769       if (!exampleReport)
2770         exampleReport = I;
2771       continue;
2772     }
2773
2774     // At this point we know that 'N' is not a sink and it has at least one
2775     // successor.  Use a DFS worklist to find a non-sink end-of-path node.
2776     typedef FRIEC_WLItem WLItem;
2777     typedef SmallVector<WLItem, 10> DFSWorkList;
2778     llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
2779
2780     DFSWorkList WL;
2781     WL.push_back(errorNode);
2782     Visited[errorNode] = 1;
2783
2784     while (!WL.empty()) {
2785       WLItem &WI = WL.back();
2786       assert(!WI.N->succ_empty());
2787
2788       for (; WI.I != WI.E; ++WI.I) {
2789         const ExplodedNode *Succ = *WI.I;
2790         // End-of-path node?
2791         if (Succ->succ_empty()) {
2792           // If we found an end-of-path node that is not a sink.
2793           if (!Succ->isSink()) {
2794             bugReports.push_back(I);
2795             if (!exampleReport)
2796               exampleReport = I;
2797             WL.clear();
2798             break;
2799           }
2800           // Found a sink?  Continue on to the next successor.
2801           continue;
2802         }
2803         // Mark the successor as visited.  If it hasn't been explored,
2804         // enqueue it to the DFS worklist.
2805         unsigned &mark = Visited[Succ];
2806         if (!mark) {
2807           mark = 1;
2808           WL.push_back(Succ);
2809           break;
2810         }
2811       }
2812
2813       // The worklist may have been cleared at this point.  First
2814       // check if it is empty before checking the last item.
2815       if (!WL.empty() && &WL.back() == &WI)
2816         WL.pop_back();
2817     }
2818   }
2819
2820   // ExampleReport will be NULL if all the nodes in the equivalence class
2821   // were post-dominated by sinks.
2822   return exampleReport;
2823 }
2824
2825 void BugReporter::FlushReport(BugReportEquivClass& EQ) {
2826   SmallVector<BugReport*, 10> bugReports;
2827   BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports);
2828   if (exampleReport) {
2829     const PathDiagnosticConsumers &C = getPathDiagnosticConsumers();
2830     for (PathDiagnosticConsumers::const_iterator I=C.begin(),
2831                                                  E=C.end(); I != E; ++I) {
2832       FlushReport(exampleReport, **I, bugReports);
2833     }
2834   }
2835 }
2836
2837 void BugReporter::FlushReport(BugReport *exampleReport,
2838                               PathDiagnosticConsumer &PD,
2839                               ArrayRef<BugReport*> bugReports) {
2840
2841   // FIXME: Make sure we use the 'R' for the path that was actually used.
2842   // Probably doesn't make a difference in practice.
2843   BugType& BT = exampleReport->getBugType();
2844
2845   OwningPtr<PathDiagnostic>
2846     D(new PathDiagnostic(exampleReport->getDeclWithIssue(),
2847                          exampleReport->getBugType().getName(),
2848                          exampleReport->getDescription(),
2849                          exampleReport->getShortDescription(/*Fallback=*/false),
2850                          BT.getCategory(),
2851                          exampleReport->getUniqueingLocation(),
2852                          exampleReport->getUniqueingDecl()));
2853
2854   MaxBugClassSize = std::max(bugReports.size(),
2855                              static_cast<size_t>(MaxBugClassSize));
2856
2857   // Generate the full path diagnostic, using the generation scheme
2858   // specified by the PathDiagnosticConsumer. Note that we have to generate
2859   // path diagnostics even for consumers which do not support paths, because
2860   // the BugReporterVisitors may mark this bug as a false positive.
2861   if (!bugReports.empty())
2862     if (!generatePathDiagnostic(*D.get(), PD, bugReports))
2863       return;
2864
2865   MaxValidBugClassSize = std::max(bugReports.size(),
2866                                   static_cast<size_t>(MaxValidBugClassSize));
2867
2868   // If the path is empty, generate a single step path with the location
2869   // of the issue.
2870   if (D->path.empty()) {
2871     PathDiagnosticLocation L = exampleReport->getLocation(getSourceManager());
2872     PathDiagnosticPiece *piece =
2873       new PathDiagnosticEventPiece(L, exampleReport->getDescription());
2874     BugReport::ranges_iterator Beg, End;
2875     llvm::tie(Beg, End) = exampleReport->getRanges();
2876     for ( ; Beg != End; ++Beg)
2877       piece->addRange(*Beg);
2878     D->setEndOfPath(piece);
2879   }
2880
2881   // Get the meta data.
2882   const BugReport::ExtraTextList &Meta = exampleReport->getExtraText();
2883   for (BugReport::ExtraTextList::const_iterator i = Meta.begin(),
2884                                                 e = Meta.end(); i != e; ++i) {
2885     D->addMeta(*i);
2886   }
2887
2888   PD.HandlePathDiagnostic(D.take());
2889 }
2890
2891 void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
2892                                   StringRef name,
2893                                   StringRef category,
2894                                   StringRef str, PathDiagnosticLocation Loc,
2895                                   SourceRange* RBeg, unsigned NumRanges) {
2896
2897   // 'BT' is owned by BugReporter.
2898   BugType *BT = getBugTypeForName(name, category);
2899   BugReport *R = new BugReport(*BT, str, Loc);
2900   R->setDeclWithIssue(DeclWithIssue);
2901   for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg);
2902   emitReport(R);
2903 }
2904
2905 BugType *BugReporter::getBugTypeForName(StringRef name,
2906                                         StringRef category) {
2907   SmallString<136> fullDesc;
2908   llvm::raw_svector_ostream(fullDesc) << name << ":" << category;
2909   llvm::StringMapEntry<BugType *> &
2910       entry = StrBugTypes.GetOrCreateValue(fullDesc);
2911   BugType *BT = entry.getValue();
2912   if (!BT) {
2913     BT = new BugType(name, category);
2914     entry.setValue(BT);
2915   }
2916   return BT;
2917 }