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