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