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