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