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