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