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