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